<백준> 전구와 스위치(Gold 5)

[백준]

2138번: 전구와 스위치

[깃허브]

ForCodeKata/baekjoon 문제집/전구와 스위치 at main · heesoo-park/ForCodeKata

제출결과

---

 

문제 자체는 매우 간결하고 바로 이해가 됐지만 이번에도 어떻게 코드로 구현해야할지가 떠오르지 않더라

어떤 알고리즘을 써야하는지 힌트를 봤는데 욕심많은 걸로만 알고있는 그리디 알고리즘이었다...

예제를 볼 때는 도저히 순차적으로 진행하는 방식이나 현재에서 가장 최선의 선택을 할 수 있는 방식이 보이지 않았다.

그래서 그냥 2중 for문을 돌려볼까 했지만 숫자 제한이나 예상 흐름을 생각했을 때 가능한 방법이 아니라는 생각이 들었다.

 

스위치를 어떤 거를 먼저 누르는지는 값을 구하는데 상관없다.

여기서 중요한 것은 '어떤 전구가 어떤 다른 전구에 영향을 주는데 어떻게 그 영향권을 한 방향으로만 세팅할 것인가?'였던 거 같다.

for문 여러번을 돌리는 건 안 되기 때문에 for문 하나로 끝내야하고 그렇다는 말은 순차적으로 흐름이 진행되서 값을 도출해내야 한다는 뜻이다.

n번째 전구의 상태를 바꿀 때 n+1번째 전구 스위치를 누르는 식으로 코드를 짠다.

여기서 순차적인 흐름을 만들기 위해서 필요한 분기 조건은 가장 첫번째 전구이다.

이 전구가 켜져있는지 꺼저 있는지에 따라서 값이 변할 수 있다.

 

그래서 첫번째 전구를 키고 진행하는 것, 끄고 진행하는 것 두가지를 돌려보고 그 결과값 2개 중에 작은 걸 최종 결과값으로 출력했다.

정말 어떻게 이런 생각을 도출해낼 수 있는지 잘 모르겠다.

저번에 다익스트라 알고리즘도 그렇지만 그리디 알고리즘도 아직 갈 길이 멀다...

 

하면서 좀 애를 먹었던 거는 처음에 String타입으로 진행했을 때 값을 변경하는게 깔끔하게 안 되는 문제, String타입에서 StringBuilder타입으로 변경했는데 모든 중간 과정이 원본 변수에까지 영향을 미치는 문제가 있었다.

그래서 마지막으로 선택한 타입은 List<Boolean>이었다.

입력을 받고 chunked함수로 자르고 map 함수를 써서 List<Boolean>으로 만들었다.

 

해당 방법으로 작성한 코드는 다음과 같다.

var answer = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    val n = readln().toInt()
    val cur = readln().chunked(1).map { it != "0" }
    val target = readln().chunked(1).map { it != "0" }

    checkLight(n, cur, target, true)
    checkLight(n, cur, target, false)

    if (answer != Int.MAX_VALUE) println(answer)
    else println(-1)
}

fun checkLight(n: Int, lights: List<Boolean>, target: List<Boolean>, isZeroReversed: Boolean) {
    var temp = lights.toMutableList()
    var cnt = 0

    if (isZeroReversed) {
        toggleLight(temp, 0)
        cnt++
    }

    for (i in 1 until n) {
        if (temp[i - 1] != target[i - 1]) {
            toggleLight(temp, i)
            cnt++
        }
    }

    if (temp == target) answer = minOf(answer, cnt)
}

fun toggleLight(lights: MutableList<Boolean>, switch: Int) {
    if (switch > 0) lights[switch - 1] = !lights[switch - 1]
    lights[switch] = !lights[switch]
    if (switch < lights.size - 1) lights[switch + 1] = !lights[switch + 1]
}

 

참고)

https://staticvoidlife.tistory.com/143

https://astrid-dm.tistory.com/429