468371. 노란불 신호등

이 문제는 각 신호등의 초록불, 노란불, 빨간불 길이가 주어졌을 때, 세 신호등이 처음으로 모두 노란불이 되는 시간을 찾아야 하는 문제이다.

처음 이 문제를 본 뒤 가장 먼저 든 생각은 시뮬레이션을 통해 시간을 늘려가며 상태를 완전탐색하는 것이었다. 그러나 문제는 시간(t)의 상한이 주어지지 않았다는 점이다. 어떻게 상한을 구할 수 있을까?

어떤 신호등의 초록불, 노란불, 빨간불의 길이가 g, y, r이라고 하면 그 신호등이 노란불이 되는 시간은 g + 1 + (g+y+r) n 으로 표현할 수 있다. 이를 다르게 표현하면 g+y+r 초 마다 주기가 반복되며 한 주기 내에서 g+1초부터 노란불이 된다.

한편 신호등이 여러 개일 때, 주기가 (r_1, r_2, ..., r_n)이라고 하면 r_i <= lcm(r_1, r_2, ..., r_n)이고 lcm(r_1, r_2, ..., r_n) % r_i = 0이다. 즉, 시간이 lcm(r_1, r_2, ..., r_n) 초가 되면 모든 신호등은 초기 상태와 똑같아진다. 바꿔 말하면 이 이후로 반복되는 패턴은 lcm초 이전에 이미 한 번 보였던 패턴이므로 우리는 lcm초를 초과하여 신호등의 패턴을 검사할 필요가 없다.

그러므로 이 문제에서 신호등의 상태를 시뮬레이션해야 할 상한은 lcm(r_1, r_2, ..., r_n)임을 알 수 있다.

🔗 문제 링크

코드

먼저 신호등의 개수와 주기를 구한다. 주기는 coeffs에 저장시킨다.

public int solution(int[][] signals) {        
    int n = signals.length;
    long[] coeffs = new long[n]; // 주기
    
    for (int i = 0; i < n; i++) {
        coeffs[i] = signals[i][0] + signals[i][1] + signals[i][2];
    }

그런 다음 앞서 언급했던 대로 탐색 상한을 확인하기 위해 모든 주기의 최소공배수를 구한다. 이후 시간 t=1에서 lim초까지 1초씩 증가시키고, 각 시간 t마다 신호등이 전부 노란색인지 확인한다. 신호등이 모두 노란색이면 t를 바로 반환하고, lim초가 될 때까지 노란색이 아니라면 모든 신호등이 노란색이 되는 경우가 없음을 확인한 것이므로 -1을 반환하게 된다.

    
    long lim = lcmAll(coeffs);
    
    for (long t = 1; t <= lim; t++) {
        for (int i = 0; i < n; i++) {
            if (!isYellow(signals[i][0], signals[i][1], signals[i][2], t))
                break;
         
            if (i == n-1) 
                return (int) t;
        }
    }
    
    return -1;
}

전체 코드

import java.util.*;

class Solution {
    long gcd(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        
        while (b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
        
        return a;
    }
    
    long lcm(long a, long b) {
        if (a == 0 || b == 0) 
            return 0;
        
        return Math.abs(a*b / gcd(a,b));
    }
    
    long lcmAll(long[] nums) {
        long result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            result = lcm(result, nums[i]);
            
            if (result == 0) {
                return 0;
            }
        }
        
        return result;
    }
    
    boolean isYellow(int g, int y, int r, long t) {
        /*
            r + g + b 
            n = (t_st - g) / (g+r+y) = ((t_ed) - (g+y))/(g+r+y)
        */
        
        long period = (long) g + y + r;
        long pos = (t) % period;
        
        return g < pos && pos <= (long) g + y;
    }
    
    public int solution(int[][] signals) {        
        int n = signals.length;
        long[] coeffs = new long[n]; // 주기
        
        for (int i = 0; i < n; i++) {
            coeffs[i] = signals[i][0] + signals[i][1] + signals[i][2];
        }
        
        
        long lim = lcmAll(coeffs);
        
        for (long t = 1; t <= lim; t++) {
            for (int i = 0; i < n; i++) {
                if (!isYellow(signals[i][0], signals[i][1], signals[i][2], t))
                    break;
             
                if (i == n-1) 
                    return (int) t;
            }
        }
        
        return -1;
    }
}

시간복잡도

시간복잡도를 대략적으로 계산해보면 $\sum \log(r_i) + n \times lcm$ => $O(n \times lcm)$ 이고, 최악의 경우(모든 주기가 소수, n=5)에도 약 100만번 정도이므로 시간초과 없이 통과할 수 있다.