[프로그래머스] 노란불 신호등

1. 문제

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

 

2. 코드

python 1

import math

def is_yellow(signal, offest):
    g, y, r = signal
    
    if g + 1 <= offest <= g + y:
        return True
    else: 
        return False

def solution(signals):
    # signals 별로의 사이클
    cycles = [sum(signal) for signal in signals]
    
    limit = math.lcm(*cycles)

    for t in range(limit):
        success = True
        for cycle, signal in zip(cycles, signals):
            offset = t % cycle
            
            if not is_yellow(signal, offset):
                success = False
                
        if success:
            return t    
            
    return -1

풀이

1. 각 신호등의 **green + yellow + red**를 더해 신호등별 순환 주기 계산
2. 모든 신호등의 상태가 다시 반복되는 시점을 구하기 위해 순환 주기의 최소 공배수(LCM)를 **limit**으로 설정
3. **0 ~ limit**까지 모든 시간을 확인
4. 현재 시간을 각 신호등의 순환 주기로 나눈 나머지를 이용해 현재 신호등의 위치 계산
5. 모든 신호등이 노란불 구간이면 해당 시간 반환
6. 끝까지 없으면 -1 반환

 

python 2

import math

def is_yellow(signal, offset):
    green, yellow, red = signal

    return green < offset <= green + yellow

def solution(signals):
    cycles = [sum(signal) for signal in signals]
    total_cycle = math.lcm(*cycles)

    for time in range(1, total_cycle + 1):
        all_yellow = True

        for cycle, signal in zip(cycles, signals):
            offset = (time - 1) % cycle + 1

            if not is_yellow(signal, offset):
                all_yellow = False
                break

        if all_yellow:
            return time

    return -1

 

3. 메모

• LCM + 완전 탐색을 통한 구현 문제
• 시간 복잡도 : O(L ×N)
  • L : 각 신호등 순환 주기의 최소 공배수
  • N : 신호등 개수
• 길이의 제한있어서 최악의 경우 20⁵ → 제한 시간 내에 전체 주기를 완전 탐색이 가능
• 해당 시간이 노란불인지를 확인해야 함
  • time % cycle로 확인 가능
• python 1에서는 offset은 0 ~ cycle-1의 범위, 노란불 범위 1기준 → python 2에서는 주기를 맞추기 위해 offset을 1 ~ cycle-1 기준으로 변경