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

문제 출처: 2025 카카오 하반기 1차  

const val GREEN = 0
const val YELLOW = 1
const val RED = 2

class Solution {
    fun solution(signals: Array<IntArray>): Int {
        var notFound: Int = -1

        val n = signals.size
        val signalList = Array(n) {
            Signal(signals[it])
        }

        var lcmOfCycle = signalList[0].cycle
        for (i in 1 until n) {
            lcmOfCycle = lcm(lcmOfCycle, signalList[i].cycle)
        }

        secondLoop@ for (second in 1..lcmOfCycle) {
            for (signal in signalList) {
                if (signal.getColor(second) != YELLOW) {
                    continue@secondLoop
                }
            }
            return second
        }

        return notFound
    }
}

class Signal(val periods: IntArray) {
    val cycle = periods[GREEN] + periods[YELLOW] + periods[RED]

    fun getColor(second: Int): Int {
        val remainder = second % cycle
        return when {
            (0 < remainder) && (remainder <= periods[GREEN]) -> GREEN
            (periods[GREEN] < remainder) && (remainder <= periods[GREEN] + periods[YELLOW]) -> YELLOW
            else -> RED
        }
    }
}

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
fun lcm(a: Int, b: Int): Int = (a * b) / gcd(a, b)

'변하지 않는 것'을 파악하는 게 중요하다. 그렇지 않으면, 문제 풀이를 위해 인식해야되는 것을 보지 못하게 된다. 복잡함이라는 이름의 미궁에 빠지기 때문이다. 또, 분기문에서 무한대 영역 또한 하나의 분기로 대해야 한다. 엄연한 가지치기의 대상인 것이다.