[코테] 노란불 신호등

출처: https://school.programmers.co.kr/learn/courses/30/lessons/468371

프로그래머스

핵심 포인트

• 각 신호등은 일정한 주기를 반복하므로, 특정 시간 t에서 각 신호등의 불빛(값)을 알 수 있음
• 각 신호등은 일정한 주기를 반복하므로, 모든 신호등의 패턴은 최소공배수(LCM)부터 동일하게 반복됨. 따라서 최대 LCM까지만 검사하면 됨
• 문제의 제한은 신호등 최대 5개, 주기(R + Y + G의 합) 최대 20이므로, 최악의 경우 LCM은 LCM(16, 17, 18, 19, 20)임. 다 곱해도 그렇게 크지 않음(320만 미만) -> Brute-Force 가능

알고리즘

LCM 계산

for 1 ~ LCM

	모든 신호등 검사
    
	하나라도 노랑이 아니면 통과
    
   	전부 노랑이면 return t
    
끝까지 없으면 return -1

코드

class Solution {

    public int solution(int[][] lights) {

        int lcm = 1;

        // 모든 신호등 주기의 최소공배수 계산
        for (int[] light : lights) {
            int cycle = light[0] + light[1] + light[2];
            lcm = lcm(lcm, cycle);
        }

        // 1초부터 최소공배수까지 검사
        for (int time = 1; time <= lcm; time++) {

            boolean allYellow = true;

            for (int[] light : lights) {
                if (!isYellow(time, light)) {
                    allYellow = false;
                    break;
                }
            }

            if (allYellow) {
                return time;
            }
        }

        return -1;
    }

    // 해당 시간에 신호등이 노란불인지 확인
    private boolean isYellow(int time, int[] light) {

        int green = light[0];
        int yellow = light[1];
        int red = light[2];

        int cycle = green + yellow + red;

        // 0부터 시작하는 위치
        int position = (time - 1) % cycle;

        return position >= green && position < green + yellow;
    }

    // 최대공약수
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    // 최소공배수
    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
}

느낀 점

• 최대공약수(gcd), 최소공배수(lcm) 구하는 공식은 외우자
• 여러 수의 최소공배수를 구하는 흐름은 외우자
• 주기가 반복되는 문제는 최소공배수가 경계값이 될 수 있음을 인지하자
• 자기 전에 코드를 다시 한 번 보고 자야겠다.