문제 출처 : 프로그래머스 > 2025 카카오 하반기 1차
난이도 : Level 1
문제 파악
신호등은 초록 → 노랑 → 빨강 순서로 반복된다.
각 신호등은 초록 상태에서 시작하며, 시작 시각은 1초이다.
문제의 목표는 모든 신호등이 동시에 노란불이 되는 가장 빠른 시각을 구하는 것이다.
만약 그런 시각이 끝까지 존재하지 않는다면 -1을 반환해야 한다.
예를 들어 다음과 같은 입력이 있다고 하자.
signals = [[2, 1, 2], [5, 1, 1]]
각 배열은 [초록, 노랑, 빨강]의 지속 시간을 의미한다.
첫 번째 신호등 [2, 1, 2]를 보면 한 주기의 길이는 5초이다.
- 1~2초: 초록
- 3초: 노랑
- 4~5초: 빨강
즉 첫 번째 신호등이 노란불이 되는 시각은
3, 8, 13, 18, 23, ... 처럼 5초 주기로 반복된다.
두 번째 신호등 [5, 1, 1]의 한 주기는 7초이다.
- 1~5초: 초록
- 6초: 노랑
- 7초: 빨강
즉 두 번째 신호등이 노란불이 되는 시각은
6, 13, 20, 27, 34, ... 처럼 7초 주기로 반복된다.
이 둘을 보면 처음으로 동시에 노란불이 되는 시각은 13초임을 알 수 있다.
언제까지 확인하면 될까?
각 신호등은 자신의 주기만큼 반복된다.
따라서 전체 신호등들의 상태 조합도 결국 반복된다.
이때 전체 패턴이 다시 처음 상태로 돌아오는 시점은
각 신호등 주기의 최소공배수이다.
위 예시에서는 주기가 5와 7이므로 최소공배수는 35이다.
즉 1초부터 35초까지만 확인해 보면 충분하다.
그 안에서 답을 찾지 못했다면, 이후에도 같은 패턴이 반복될 뿐이므로 정답은 없다.
따라서 -1을 반환하면 된다.
해결 아이디어
이 문제는 특정 시각 t에서 모든 신호등이 동시에 노란불인지 판별하는 문제이다.
따라서 각 시각마다 다음과 같은 방식으로 판단한다.
먼저 all_yellow라는 변수를 두고,
현재 시각 t에서 모든 신호등이 노란불이라고 가정한 뒤 시작한다.
그리고 signals를 순회하면서,
하나라도 노란불이 아닌 신호등이 나오면 all_yellow를 False로 바꾸고
더 이상 확인할 필요 없이 반복문을 종료한다.
반대로 signals를 끝까지 모두 확인했는데도
all_yellow가 여전히 True라면
그 시각이 바로 모든 신호등이 동시에 노란불이 되는 가장 빠른 시각이다.
그렇다면 핵심은 다음 질문으로 이어진다.
👉 특정 시각 t에서, 한 신호등이 노란불인지 어떻게 판단할까?
각 신호등은 [초록, 노랑, 빨강]으로 이루어진 주기를 반복한다.
따라서 시각 t를 그대로 사용하는 것이 아니라,
현재 주기 안에서 몇 번째 위치인지로 변환해야 한다.
이를 위해 다음 공식을 사용한다.
pos = (t - 1) % cycle + 1
이 값은 시각 t를 주기 안의 위치(1 ~ cycle)로 변환해준다.
이제 신호등 [g, y, r]에 대해 구간을 나누면 다음과 같다.
- 초록: 1 ~ g
- 노랑: g + 1 ~ g + y
- 빨강: g + y + 1 ~ g + y + r
따라서 pos가 다음 범위에 있으면 노란불이다.
g + 1 <= pos <= g + y
해답 코드
import math
def solution(signals):
# 각 신호등의 주기 계산
cycles = []
for signal in signals:
cycles.append(sum(signal))
# 전체 패턴이 반복되는 최소공배수 계산
lcm = 1
for num in cycles:
lcm = lcm * num // math.gcd(lcm, num)
# 1초부터 최소공배수 시각까지 확인
for t in range(1, lcm + 1):
all_yellow = True
for g, y, r in signals:
cycle = g + y + r
pos = (t - 1) % cycle + 1
# 현재 시각이 노란불 구간이 아니면 실패
if not (g + 1 <= pos <= g + y):
all_yellow = False
break
# 모든 신호등이 노란불이면 즉시 반환
if all_yellow:
return t
return -1마무리
이 문제는 처음 보면 노란불이 나오는 시각을 각각 직접 나열해서 공통 시점을 찾고 싶어질 수 있다.
하지만 그렇게 풀기보다는, 반복되는 주기의 성질을 이용해 최소공배수까지만 탐색하면 훨씬 깔끔하게 해결할 수 있다.
또한 pos = (t - 1) % cycle + 1 공식을 통해
현재 시각을 한 주기 안의 위치로 바꾸는 아이디어가 핵심이었다.
정리하면 이 문제는
- 반복되는 주기 찾기
- 최소공배수까지 탐색하기
- 현재 시각이 노란불 구간인지 판별하기
이 세 가지를 정확히 구현하는 문제였다.
다음날 푼 코드
import math
def solution(signals):
# 최소공배수 구하기
cycles = []
for signal in signals:
cycles.append(sum(signal))
lcm = 1
for cycle in cycles:
lcm = lcm * cycle // math.gcd(lcm, cycle)
# 모두가 옐로우가 되는 구간 찾기
for time in range(1,lcm + 1):
all_yellow = True
for g,y,r in signals:
cycle = g + y + r
pos = (time-1) % cycle + 1
if not (g < pos < g + y + 1):
all_yellow = False
break
if all_yellow:
return time
return -1 