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

문제 조건에는 신호의 지속 시간이 정해져있지 않으므로 시간은 무한으로 흐를 수 있다. 즉 각 신호등은 시간의 흐름에 따라 특정 주기(초록불, 노란불, 빨간불의 지속 시간의 합)로 신호를 반복한다. 이때, 유한한 시간을 범위로 놓고 판단할 필요가 있는데, 이 범위는 세 신호등의 최소 공통 주기가 될 것이다. 즉, 모든 신호등이 노란불이 되는 경우가 존재한다면, 그 경우는 세 신호등 주기의 최소 공배수를 내에 있을 것이다.

알고리즘 분류는 '수학을 곁들인 완전탐색' 정도로 볼 수 있을 것 같다.

🤔개념

우선 파이썬에서 최소공배수를 구하는 방법을 알아보자.

파이썬에서 최소공배수 구하기

math.lcm() 함수 사용 (Python 3.9 버전 이상)

  import math

  # 12와 18의 최소공배수 구하기
  result = math.lcm(12, 18)
  print(result)  # 출력: 36

math.gcd() 함수 활용

gcd 함수로 최대공약수를 먼저 구한 뒤, 두 수의 곱을 최대공약수로 나눌 수 있다.

import math

a = 12
b = 18
# math.gcd로 최대공약수를 구해 활용
lcm = (a * b) // math.gcd(a, b)
print(lcm)  # 출력: 36

여러 수의 최소공배수 구하기

math.lcm 은 여러 인자를 한 번에 계산할 수 있다 (Python 3.9 버전 이상).

import math

# 12, 18, 24의 최소공배수
result = math.lcm(12, 18, 24)
print(result)  # 출력: 72

3.9 미만 버전 또는 함수 구현

math.gcd 만 사용 가능한 경우, functools.reduce 를 사용하여 리스트 전체의 최소공배수를 구할 수 있다.

import math
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm, numbers)

print(lcm_list([12, 18, 24]))  # 출력: 72

프로그래머스의 파이썬 버전은 3.8(26.03 기준)이다.

카카오 코테 당시의 버전은 3.9 이상이었던걸로 기억하긴 한다.

☺️풀이

나의 풀이

각 신호등에 대한 노란불이 켜지는 시간을 배열로 따로 저장했다.

import math
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm, numbers)

def solution(signals):
    answer = 0
    주기s=[]
    for 초,노,빨 in signals:
        주기=초+노+빨
        주기s.append(주기)
    최소공통주기=lcm_list(주기s)

    노란불켜지는시간=[[0]*(최소공통주기+1) for _ in range(len(signals))]
    
    for i,sig in enumerate(signals):
        초,노,빨=sig
        주기=주기s[i]
        k=0
        while True:
            s=초+1+주기*k
            e=초+노+주기*k
            if 최소공통주기<s:
                break
            # 노란불이 켜진 시간 범위만큼 해당 시각들은 0->1 변환
            for j in range(s,e+1):
                노란불켜지는시간[i][j]=1
            k+=1
	
    for 시각 in range(1,최소공통주기+1):
        cnt=0
        신호등갯수=len(signals)
        for sig in range(신호등갯수):
            if 노란불켜지는시간[sig][시각]==1:
                cnt+=1
        if cnt==신호등갯수:
            answer=시각
            break
    else:
        answer=-1
        
    return answer

채점 결과

다른 사람의 풀이

나머지를 활용한 다른 사람의 풀이를 참고하여 풀이를 보완해보았다.

# 다른 사람 풀이 참고: 나머지 활용
import math
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm,numbers)

def solution(signals):
    answer = 0
    주기s=[초+노+빨 for 초,노,빨 in signals]
    최소공통주기=lcm_list(주기s)

    for 시각 in range(1, 최소공통주기+1):
        모두노란불=True

        for 초,노,빨 in signals:
            주기=초+노+빨
            mod=시각%주기 # 나머지로 판단
			
            # 신호등 중 하나라도 해당 시각에 노란불이 아니면 나가리
            if not (초<=mod<=초+노-1):
                모두노란불=False
                break
                
        if 모두노란불:
            return 시각+1
    
    return -1

채점결과

나머지를 활용하면 시간/공간복잡도를 훨씬 줄일 수 있음을 확인할 수 있다.