노란불 신호등

문제

어떤 도로에 차량 신호등이 N개 있습니다. 모든 신호등은 항상 '초록불 → 노란불 → 빨간불' 순서로 반복되며, 각 신호의 지속 시간은 신호등마다 다릅니다. 시간은 1초부터 시작하며, 각 신호등은 처음에는 초록불 상태로 시작합니다. 이 도로에서 모든 신호등이 동시에 노란불이 되면 정전이 발생합니다. 주어진 신호 주기 데이터를 바탕으로 모든 신호등이 노란불이 되는 가장 빠른 시각(초)을 구하는 프로그램을 작성하는 문제입니다. 만약 그런 경우가 없다면 -1을 반환합니다.

• 입력: 신호등 n개의 신호 주기를 담은 2차원 정수 배열 signals (2 ≤ n ≤ 5). 각 원소는 [초록, 노란, 빨간] 형태의 지속 시간을 나타냅니다.
• 출력: 모든 신호등이 노란불이 되는 가장 빠른 시각(초)을 반환합니다. (불가능할 경우 -1)

풀이: 주기를 활용한 배열 전개와 완전 탐색

각 신호등의 한 사이클(초록+노란+빨간)을 리스트에 전개하여 상태를 기록하고, 나올 수 있는 전체 시간의 경우의 수를 모두 탐색하는 직관적인 브루트포스 풀이입니다.

• 신호 주기 전개 (Unrolling): 각 신호등의 주기를 List에 0(초록), 1(노란), 2(빨간) 형태로 저장합니다. 예를 들어 2초/1초/2초라면 [0, 0, 1, 2, 2]로 저장되어 인덱스(시간)로 상태에 쉽게 접근할 수 있습니다.
• 최대 탐색 범위 설정 (maxT): 모든 신호등이 원래의 상태로 동시에 돌아오는 시점은 각 주기의 최소공배수(LCM)입니다. 하지만 문제의 제한사항에서 각 주기의 최대 길이는 20이고, 신호등은 최대 5개이므로, 단순히 모든 주기를 곱한 값($20^5 = 3,200,000$)까지 탐색해도 제한 시간 내에 충분히 완전 탐색이 가능합니다.
• 완전 탐색 (Simulation): t = 0부터 maxT - 1까지 1초씩 시뮬레이션합니다.
  • 각 신호등의 현재 상태는 t % 해당 신호등의 주기 길이 인덱스를 통해 확인합니다.
  • 첫 번째 신호등이 노란불(1)이 아니라면 굳이 다른 신호등을 검사할 필요 없이 즉시 패스(continue)합니다.
  • 모든 신호등의 상태가 일치하여 모두 노란불임이 확인되면, 문제의 기준인 1초부터 시작하는 시간에 맞추어 t + 1을 반환합니다.
• 불가능한 경우: 최대 탐색 범위인 maxT까지 확인했는데도 조건이 맞지 않는다면, 영원히 모든 신호등이 동시에 노란불이 될 수 없음을 의미하므로 -1을 반환합니다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] signals) {
        int n = signals.length;
        List<Integer>[] lists = new ArrayList[n];
        
        for (int i = 0; i < n; i++) {
            lists[i] = new ArrayList<>();
        }
        
        // 0: 초록불, 1: 노란불, 2: 빨간불로 각 주기를 리스트에 저장
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < signals[i][j]; k++) {
                    lists[i].add(j);
                }
            }
        }
        
        // 모든 주기의 곱을 구하여 최대 탐색 시간(maxT) 설정
        int maxT = 1;
        for (int i = 0; i < n; i++) {
            maxT *= lists[i].size();
        }
        
        // 0초부터 maxT - 1초까지 모든 시간 탐색
        for (int t = 0; t < maxT; t++) {
            // 첫 번째 신호등이 노란불(1)이 아니면 바로 다음 시간으로 패스 (최적화)
            int tmp = lists[0].get(t % lists[0].size());
            if (tmp != 1) continue;
            
            boolean flag = true;
            // 나머지 신호등 상태 확인
            for (int i = 1; i < n; i++) {
                if (tmp != lists[i].get(t % lists[i].size())) {
                    flag = false;
                    break;
                }
            }
            
            // 모든 신호등이 노란불이면 현재 시간 + 1 반환 (1초부터 시작하므로)
            if (flag) {
                return t + 1;
            }
        }
        
        return -1; // 모든 신호등이 노란불이 되는 경우가 존재하지 않음
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 시뮬레이션 (Simulation)