프로그래머스 신호등 정전 JAVA 풀이 (시뮬레이션, 최소공배수)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

신호등마다 초록불 → 노란불 → 빨간불 순서로 반복되며, 각각의 지속 시간이 다르게 주어진다.

모든 신호등은 1초부터 초록불 상태로 시작한다.

 

모든 신호등이 동시에 노란불이 되는 가장 빠른 시간을 구하고, 그런 시간이 없다면 -1을 반환하는 문제이다.

---

📌 접근 방법

각 신호등은 자신의 주기(G + Y + R) 를 반복한다.

따라서 특정 시간 t에서 신호등의 상태는 현재 시간이 아니라 주기 내부의 몇 번째 초인지만 알면 판단할 수 있다.

 

모든 신호등의 상태는 각 주기의 최소공배수(LCM) 마다 동일하게 반복된다.

따라서 1초부터 LCM까지 모든 시간을 확인하면 반드시 정답을 찾거나 존재하지 않는다는 것을 알 수 있다.

 

매 시간마다 모든 신호등이 노란불인지 확인하고, 처음 만족하는 시간을 반환한다.

---

📌 핵심 아이디어

1. 신호등의 한 주기 계산

신호등은 자신의 주기를 계속 반복한다.

cycle = G + Y + R;

---

2. 현재 시간을 주기 내부 시간으로 변환

time = (t - 1) % cycle + 1;

예를 들어

주기 = 5

t = 1 → 1
t = 5 → 5
t = 6 → 1
t = 7 → 2

처럼 항상 현재 주기 안에서의 시간을 구할 수 있다.

---

3. 노란불 구간 판별

노란불

G + 1
~
G + Y

 

if (time > G && time <= G + Y)

 

---

4. 최소공배수까지만 탐색

각 신호등의 상태는 자신의 주기로 반복된다.

여러 신호등의 전체 상태는 모든 주기의 최소공배수마다 다시 동일해진다.

lcm = lcm(lcm, cycle);

따라서

1 ~ LCM

까지만 탐색하면 충분하다.

---

📌 전체 코드

class Solution {

        public int solution(int[][] signals) {
            int lcm = 1;

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

            // 1초부터 LCM까지 탐색
            for (int t = 1; t <= lcm; t++) {
                boolean allYellow = true;

                for (int[] signal : signals) {
                    int g = signal[0];
                    int y = signal[1];
                    int cycle = g + y + signal[2];

                    // 현재 주기에서 몇 번째 초인지 계산
                    int time = (t - 1) % cycle + 1;

                    // 노란불이 아니면 종료
                    if (!(time > g && time <= g + y)) {
                        allYellow = false;
                        break;
                    }
                }

                if (allYellow) {
                    return t;
                }
            }

            return -1;
        }

        // 최대공약수
        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;
        }
    }

 

---

📄 정리

• 신호등은 각각 자신의 주기를 반복한다.
• 현재 시간을 주기 내부 시간으로 변환하면 현재 신호를 쉽게 판별할 수 있다.
• 모든 신호등의 상태는 최소공배수마다 반복된다.
• 최대 주기가 작기 때문에 LCM 범위 내에서 완전 탐색으로 해결 가능하다.