[프로그래머스/C++] [1차] 추석 트래픽

 

 

문제

문제 설명

 

 

풀이

 

 

[문제 풀이]

 

정렬을 한 뒤, deque를 써서 문제를 풀었다. 

 

특정 시간에 최대 몇개가 포함되어 있는지 풀면 되는 문제기 때문에 먼저 시작 시간을 기준으로 정렬을 했다.

 

이후 시작시간을 기준으로 정렬을 했기 때문에 끝나는 시간이 deque의 맨 앞에 저장 된 시작 시간 보다 더 크다면 마찬가지로 같은 시간에 처리가 되고 있다는 뜻이다.

 

이후 끝나는 시간이 가장 빠른 처리가 맨 앞으로 와야 하므로 deque의 원소와 비교해 처리가 끝나는 시간을 비교하고 올바른 위치에 삽입했다.

 

위치를 바꿔서 삽입해도 되는 이유는 항상 deqeu의 맨 앞에 끝나는 시간이 가장 빠른 트래픽이 오도록 정렬해 두었기 때문에 가능한 것이다.

 

​

[아이디어 정리]

1. 시작 시간을 기준으로 트래픽을 정렬한다.
2. 이후 deque를 활용해 맨 앞에 끝나는 시간이 가장 빠른 트래픽이 오게 하고, 현재 트래픽의 시작시간이 deque의 맨 앞 원소보다 트래픽이 작으면 삽입, 크면 deque의 원소를 삭제한다.
3. deque에 삽입할 때는 끝나는 시간을 비교해 현재 트래픽을 집어넣는다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include<iostream>
using namespace std;

vector<pair<int,int>> timeTable;
void convTime(string timeS)
{
    int stTime=0;
    int edTime=0;
    edTime+=stoi(timeS.substr(0,2))*3600;
    edTime+=stoi(timeS.substr(3,2))*60;
    edTime+=stoi(timeS.substr(6,2));
    edTime*=1000;
    int tt = stoi(timeS.substr(9,3));
    edTime+=tt;
    int cc =timeS.substr(13).size();
    tt = stof(timeS.substr(13,cc))*1000;
    stTime=edTime-(tt)+1;
    edTime+=999;
    timeTable.push_back(make_pair(stTime,edTime));
}
bool compare(pair<int,int> a,pair<int,int> b)
{    
    return a.first<b.first;
}

int solution(vector<string> lines) {
    int answer=1;
    int maxStTime=3600*24*1000+1001;
    int nowCnt;
    for (int i=0; i<lines.size(); i++)
    {
        convTime(lines[i].substr(11));
    }
    sort(timeTable.begin(),timeTable.end(),compare);
    deque<pair<int,int>> Deq;
    pair<int,int> comp;
    for (int i=0; i<timeTable.size(); i++)
    {
        comp=timeTable[i];
        if (Deq.size()>answer)
        {
            answer=Deq.size();
        }
        while(true)
        {
            if (Deq.empty())
            {
                Deq.push_back(comp);
                break;
            }
            if (Deq.front().second>=comp.first)
            {
                int instN=Deq.size();
                for (int i=0; i<Deq.size(); i++)
                {
                    if (Deq[i].second>comp.second)
                    {
                        instN=i;
                        break;
                    }
                }
                Deq.insert(Deq.begin()+instN,comp);
                if (Deq.size()>answer)
                {
                    answer=Deq.size();
                }
                break;
            }
            else
            {   
                Deq.pop_front();
            }
        }
    }
    return answer;
}

 

---

 

하... 이 문제를 풀면서 스트레스를 받을 뻔했다.

 

문제에 주어진 트래픽은 끝나는 시간이 기준인데 내 마음대로 시작시간에 더하나 끝나는 시간에 더하나 범위니까 똑같겠지 라고 생각하고 트래픽의 끝나는 시간에 처리시간을 더했다... 그랬더니 당연한 이야기지만 문제가 안풀렸다

문제는 내가 문제를 이상하게 풀고있다는 사실을 거의 1시간이 지나서야 눈치챘다;;;

 

이후 다시 문제를 푸는데 왜 안풀리지 하고 이것저것 만져보다가 코드가 처음 풀이에서 많이 바뀌었고, 다시 deque로 풀기 위해 여러가지 조건을 세우다 보니 머리도 어지러워졌다...

다음부터는 곱게 문제에 나온대로 풀도록...

 

프로그래머스