문제

https://softeer.ai/practice/6256

---

입력

첫 번째 줄에 N이 주어진다. 다음 N개의 줄 중 i (1 ≤ i ≤ N)번째 줄에는 ti와 wi가 공백 하나를 사이로 두고 주어진다.

---

출력

첫 번째 줄에 N개의 정수를 공백 하나씩을 사이로 두고 출력한다. 이 중 i (1 ≤ i ≤ N)번째 정수는 i번 차량이 도로를 통과한다면 교차로를 통과하는 시각, 교차로를 통과하지 않는다면 -1이어야 한다.

---

풀이

제한조건

• 2 ≤ N ≤ 200,000
• 모든 i(1 ≤ i ≤ N)에 대해, 0 ≤ ti ≤ 109이고, wi는 A, B, C, D 중 하나이다.
• t1 ≤ t2 ≤ ... ≤ tN
• i ≠ j 이고 ti = tj이면, wi ≠ wj이다.

접근방법

Queue를 적절히 활용해야 한다.

가장 조심할 점은 시간을 관리하는 부분이다.
시간의 최대가 10^9 까지 있으므로, 1씩 모든 시간대를 확인하다가는 반드시
시간초과를 맞는다.

1. 각각의 방향에 따른 Queue를 선언한다.
	a. 12시방향 부터 시계방향으로 0123순으로 부여하면 (i+3) % 4로 오른쪽을 확인 할 수 있다.
2. 차량 통과 여부 확인
	a. 4개의 큐가 모두 비었다면, 모두 통과.
    b. 4개의 큐가 전부 대기중이라면, 교착상태.
    c. 통행가능 여부를 체크하고 1대씩 통과시킨다.

어떻게 시간을 관리할 것인지에 유의하며 코드를 작성하자.
주석참고!

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static class Car {
		int id;
		int inTime;

		Car(int a, int b) {
			id = a;
			inTime = b;
		}
	}

	static int N;
    static int[] arr;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(in.readLine());
        arr = new int[N];
        Arrays.fill(arr, -1);
		Queue<Car>[] q = new Queue[4];
		for (int i = 0; i < 4; ++i)
			q[i] = new ArrayDeque();

		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
            int dir = inputs[1].charAt(0) - 'A';
			q[dir].add(new Car(i, stoi(inputs[0])));
		}

        int currentTime = -1;
        while(true){
        	// 모든 차량이 통과하였음.
            if(q[0].isEmpty() && q[1].isEmpty() && q[2].isEmpty() && q[3].isEmpty())
                break;

            int[] state = new int[4];
            int minTime = Integer.MAX_VALUE;
            for(int i = 0; i < 4; ++i){
                if(!q[i].isEmpty()){
                    int t = q[i].peek().inTime;
                    minTime = Math.min(t, minTime);
                    if(t <= currentTime)
                        state[i] = 1;
                }
            }
            int count = 0;
            for(int value : state)
                count += value;
            
            if(count == 0){
            	// 어떤 차량도 아직 교차로에 진입하지 않음.
                // 가장 빠른 차량의 시간으로 점프
                currentTime = minTime;
            } else if(count == 4)
            	// 모든 차량에 교차로에서 대기중 -> 교착상태
                break;
            else{
                for(int i = 0; i < 4; ++i){
                    // 현재 방향에서 진행 가능하며, 오른쪽은 불가능 할 때
                    if(state[i] != 0 && state[(i+3) % 4] == 0){
                        arr[q[i].poll().id] = currentTime;
                    }
                }
                currentTime += 1;
            }
        }
        
		for (int i = 0; i < N; ++i)
			sb.append(arr[i]).append("\n");

		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

시간초과 코드

import java.io.*;
import java.util.*;

public class Main {
	static class Car {
		int id;
		int inTime;
		int outTime;
		int dir;

		Car(int a, int b, char c) {
			id = a;
			inTime = b;
			outTime = -1;
			dir = c - 'A';
		}
	}

	static int N;
	static Car[] carArr;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(in.readLine());

		carArr = new Car[N];
		Queue<Car>[] q = new Queue[4];
		for (int i = 0; i < 4; ++i)
			q[i] = new ArrayDeque();

		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			carArr[i] = new Car(i, stoi(inputs[0]), inputs[1].charAt(0));
			q[carArr[i].dir].add(carArr[i]);
		}

		int t = 0;
		int[] state = new int[4];
		while (true) {
			// 모든 차량이 통과했다.
			if (q[0].isEmpty() && q[1].isEmpty() && q[2].isEmpty() && q[3].isEmpty())
				break;

			int count = 0;
			for (int i = 0; i < 4; ++i){
				state[i] = exist(q[i], t);
				if(state[i] != -1)
					count++;
			}

			// 모두 대기중이라면 교착상태
			if (state[0] != -1 && state[1] != -1 && state[2] != -1 && state[3] != -1)
				break;

			for (int i = 0; i < 4; ++i) {
				// 해당 방향에 차량이 대기중
				if (state[i] != -1) {
					// 오른쪽 차량도 대기중인경우
					if (state[(i + 3) % 4] != -1)
						continue;
					count--;
					carArr[q[i].poll().id].outTime = t;

					// 반대쪽 차량도 진행 할 수 있는 경우
					if (state[(i + 2) % 4] != -1 && state[(i + 1) % 4]  == -1) {
						carArr[q[(i + 2) % 4].poll().id].outTime = t;
						count--;
					}
					break;
				}
			}

			if(count > 0){
				t++;
			}else{
				int min = 500000;
				for(int i = 0; i < 4; ++i){
					if(!q[i].isEmpty() && q[i].peek().inTime != -1)
						min = Math.min(min, q[i].peek().inTime);
				}
				t = min;
			}
		}
		for (int i = 0; i < N; ++i)
			sb.append(carArr[i].outTime).append("\n");

		System.out.println(sb);
	}

	public static int exist(Queue<Car> q, int time) {
		if (q.isEmpty())
			return -1;
		if (time < q.peek().inTime)
			return -1;
		return q.peek().inTime;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}