소프티어 [HSAT 3회 정기 코딩 인증평가 기출] 교차로 (C++)

 

문제 )

https://softeer.ai/practice/6256

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

설명 )

시뮬레이션의 문제..전체 입력을 q라는 이름의 q로 받고, 입력시간마다 꺼내서 각 도로에 맞는 A,B,C,D라는 이름의 큐에 push해주었다. 

그리고 A,B,C,D의 큐가 비었는지 아닌지 여부에따라 행동 방식을 결정하였다.

첫번째 풀이가 시간초과가 나서 결국검색했는데, A,B,C,D 교차로가 비어있는 SKIP 해주는 방식으로 최적화를 하니 시간초과를 피할 수 있었다. 

A,B,C,D가 비어있는 경우, 현재 시간을 q 큐의 맨앞 차량의 시간으로 갱신해주면 도로가 비어있는 시간을 없앨 수 있다. 

 

 

코드 )

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <tuple>


int N;
int answer[200000];
using namespace std;
queue <tuple <int, int,int>> q,A,B,C,D;
bool deadlock = false;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t = 0;
    cin >> N;

    int time;
    char w;
    int idx;
    for (int i = 0; i < N; ++i) {
        cin >> time >> w;
        q.push({time, w, i});
    }

    while(1){
        while(!q.empty()) {
                tie(time,w,idx) = q.front();
                if(time != t) break;
                q.pop();
                if (w == 'A')
                    A.push({time, w, idx});
                else if (w == 'B')
                    B.push({time, w, idx});
                else if (w == 'C')
                    C.push({time, w, idx});
                else if (w == 'D')
                    D.push({time, w, idx});
        }

        if(A.empty() && B.empty() && C.empty() && D.empty()) {
            tie(time,w,idx) = q.front();
            t = time;
            continue;
        }
        bool flagA = false;
        bool flagB = false;
        bool flagC = false;
        bool flagD = false;


        if(!A.empty() && D.empty())
        {
            tie(time,w,idx) = A.front();
            answer[idx] = t;
            flagA = true;
        }
        if(!B.empty() && A.empty())
        {
            tie(time,w,idx) = B.front();
            answer[idx] = t;
            flagB = true;
        }
        if(!C.empty() && B.empty())
        {
            tie(time,w,idx) = C.front();
            answer[idx] = t;
            flagC = true;
        }
        if(!D.empty() && C.empty())
        {
            tie(time,w,idx) = D.front();
            answer[idx] = t;
            flagD = true;
        }

        if(flagA) A.pop();
        if(flagB) B.pop();
        if(flagC) C.pop();
        if(flagD) D.pop();

        if(!A.empty() && !B.empty() && !C.empty() && !D.empty()) {
            deadlock = true;
            break;
        }


        if(q.empty() && A.empty() && B.empty() && C.empty() && D.empty())
            break;


        t++;
    }


    if(deadlock){
        while(!A.empty()){
            tie(time,w,idx) = A.front();
            answer[idx] = -1;
            A.pop();
        }
        while(!B.empty()){
            tie(time,w,idx) = B.front();
            answer[idx] = -1;
            B.pop();
        }
        while(!C.empty()){
            tie(time,w,idx) = C.front();
            answer[idx] = -1;
            C.pop();
        }
        while(!D.empty()){
            tie(time,w,idx) = D.front();
            answer[idx] = -1;
            D.pop();
        }
        while(!q.empty()){
            tie(time,w,idx) = q.front();
            answer[idx] = -1;
            q.pop();
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << answer[i] <<"\n";
    }
}