프로그래머스 level 1 노란불 신호등 2025 카카오 하반기 1차

문제 설명

어떤 도로에 차량 신호등이 n개 있습니다. 모든 신호등은 항상 초록불 → 노란불 → 빨간불 순서로 반복되며, 각 신호의 지속 시간은 신호등마다 다릅니다. 시간은 1초부터 시작하며, 각 신호등은 처음에는 초록불 상태로 시작합니다.

 

이 도로에서는 가끔 정전이 일어나는데, 모든 신호등이 모두 노란불이 되면 정전이 발생한다는 사실이 밝혀졌습니다.

 

예를 들어 신호등이 2개이고, 각 신호등의 주기가 다음과 같다고 가정해 보겠습니다.

신호등	초록불	노란불	빨간불
1번	2초	1초	2초
2번	5초	1초	1초

 

위 그림과 같이 13초에 처음으로 두 신호등이 모두 노란불이 됩니다. 

 

신호등 n개의 신호 주기를 담은 2차원 정수 배열 signals가 매개변수로 주어집니다.

모든 신호등이 노란불이 되는 가장 빠른 시각(초)을 return 하도록 solution 함수를 완성해 주세요.

만약 모든 신호등이 노란불이 되는 경우가 존재하지 않는다면 -1을 return 해주세요.

 

제한사항

• 2 ≤ signals의 길이 = n ≤ 5
  • signals의 원소는 [G, Y, R] 형태의 길이가 3인 정수 배열입니다. 순서대로 초록불, 노란불, 빨간불의 지속 시간을 의미합니다.
  • 1 ≤ G, Y, R ≤ 18
  • 3 ≤ G + Y + R ≤ 20

 

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다.

각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

 

그룹	총점추가	제한사항
#1	30%	신호등이 모두 노란불이 되는 시각이 20 이하인 정답이 존재합니다.
#2	30%	신호등이 모두 노란불이 되는 경우가 존재합니다.
#3	40%	추가 제한 사항 없음

 

입출력

입출력 예	result
[[2, 1, 2], [5, 1, 1]]	13
[[2, 3, 2], [3, 1, 3], [2, 1, 1]]	11
[[3, 3, 3], [5, 4, 2], [2, 1, 2]]	193
[[1, 1, 4], [2, 1, 3], [3, 1, 2], [4, 1, 1]]	-1

입출력 예시 설명

입출력 예 #1  문제 설명의 예시와 같습니다.

입출력 예 #2

신호등	초록불	노란불	빨간불
1번	2초	3초	2초
2번	3초	1초	3초
3번	2초	1초	1초

11초에 3개의 신호등이 모두 노란불이 됩니다.

 

입출력 예 #3

신호등	초록불	노란불	빨간불
1번	3초	3초	3초
2번	5초	4초	2초
3번	2초	1초	2초

193초에 3개의 신호등이 모두 노란불이 됩니다.

 

입출력 예 #4

모든 신호등이 노란불이 되는 경우가 존재하지 않으므로 -1을 return 해야 합니다.

 

 

---

코드작성

- 초반

초반에는 cycle이 20 이하이고 아무리 해봤자 최소공배수까지기 때문에,

 

1) 각 신호등별로 노란불이 나오는 시간 리스트를 만듦

2) 그게 없다면 노란불이 겹치는 시간이 없는 것이니 -1을 리턴

3) 그렇지 않다면 동시에 노란물이 나오는 시간을 매칭하여 첫번째 교차시간을 출력

 

아래와 같이 코드를 작성하였다.

 

첫번째로 나오는 노란색 신호등, 그 노란 신호등이 돌아오는 주기, 리미트를 설정하고

첫번째 노란 신호등부터 리미트까지 주기를 for문으로 돌게 하였다.

이때, 노란불이 시작되는 시간부터 노란불이 유지되는 시간만큼 반복했다.

예를 들어 노란불이 6초에 시작되고 4초 동안 유지된다면, 리스트에는 6, 7, 8, 9가 추가된다.

 

이 과정을 신호등의 한 주기인 cycle만큼 건너뛰면서 반복하면, 해당 신호등이 리미트 이내에 노란불이 되는 모든 시간을 구할 수 있다.

 

def make_yellow(signal):
    yellow_lights = []

    green, yellow, red = signal    
    first_yellow = green + 1
    cycle = green + yellow + red
    limit = 9999

    for start in range(first_yellow, limit + 1, cycle):
        for t in range(start, start + yellow):
            if t <= limit:
                yellow_lights.append(t)
    return yellow_lights

def solution(signals):
    yellow_list = []
    for signal in signals:
        yellow_lights = make_yellow(signal)
        yellow_list.append(yellow_lights)
        
    if not yellow_list:
        return -1
    
    matched = set(yellow_list[0])
    
    for lst in yellow_list[1:]:
        matched &= set(lst)
        
    matched = sorted(matched)
        
    if matched:
        return matched[0]
    else:
        return -1

 

 

예시는 다 맞았으나 문제는 테스트케이스가 60/100점이 나왔다.

 

의심스러웠던건 `limit` 과 `노란불을 담은 누적 리스트`이었다.

 

 

- 리스트에서 불리안 형태로 변환

따라서 우선 limit은 두고, 누적 리스트를 불리안 형태로 변형하여 풀어봤다.

 

특히 이중 FOR문을 돌아서 비효율적이었던 코드를 `position = (t-1) % cycle + 1`로 변환하여 효율을 높였다.

그렇게 구한 position이 초록불 이후, 노란불이 끝나기 전. 즉, 노란불이 유지되는 시간에 없다면 false를, 그렇지 않다면 true로 설정하여 true일때 초(t)를 리턴하게 했다.

 

def solution(signals):
    limit = 100000

    for t in range(1, limit+1):
        all_yellow = True
        
        for signal in signals:
            green, yellow, red = signal
            cycle = green + yellow + red
            position = (t-1) % cycle + 1
            
            if not (green < position <= green + yellow):
                all_yellow = False
                break
                
        if all_yellow:
            return t
        
    return -1

 

예시는 전부 정답이었으나 테스트케이스에서는 60/100을 받았다.

 

따라서 결론적으로 문제는 `limit`을 처리하는 방법이 잘못됐다는 것을 깨달았다.

 

 

- 결국 맨처음 생각했던 최소공배수

limit을 1부터 시작해서 늘리지 않는다면..

접근할 수 있는 경로는 최소공배수 하나 뿐이다.

 

직전 코드에서 작성했던 노란불 신호등 구하기는 냅두고, `limit`을 1로 설정해서 주기의 최소공배수로 변환하여 불리안으로 true값을 처리하게 한다.

from math import gcd

def lcm(a, b):
    return a * b // gcd(a,b)

def is_yellow(t, signal):
    green, yellow, red = signal
    cycle = green + yellow + red
    position = (t - 1) % cycle + 1
    
    return green < position <= green + yellow

def solution(signals):
    limit = 1
    
    for signal in signals:
        green, yellow, red = signal
        cycle = green + yellow + red
        limit = lcm(limit, cycle)
        
    for t in range(1, limit + 1):
        if all(is_yellow(t, signal) for signal in signals):
            return t
    return -1