<백준> 톱니바퀴(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%ED%86%B1%EB%8B%88%EB%B0%94%ED%80%B4

[백준]

https://www.acmicpc.net/problem/14891

제출 결과

 

끝내 풀어냈노라...!!

진짜 이 악물고 고치고 합치고 쓰고 반례 뒤지면서 해결했다.

지금도 머릿속에서 톱니바퀴가 도는것만 같다...

 

이 문제는 주어진대로 구현하는 문제였어서 어떻게 해야하나 고민이 들었는데 그냥 그대로 코드를 적었다.

여기서 톱니바퀴가 특이했던 건 극성이 있어서 같은 극일 때는 옆의 톱니바퀴가 돌아가도 영향을 안 받고 다른 극일 때 영향을 받는다는 거였다.

 

처음에 톱니바퀴의 극성을 저장해야했는데 그건 StringBuilder를 사용하기로 했다.

워낙에 톱니바퀴가 많이 돌 것으로 예상되기 때문에 그냥 String이나 Array 썼다가는 컴퓨터가 힘들어할 거 같기 때문이었다.

 

입력을 쭉 받고 이제 톱니바퀴를 돌릴 시간이 왔다.

나의 첫 아이디어는 뭔가 재귀로 첫 톱니바퀴를 돌리고~ 연결된 톱니바퀴 돌리고~ 였는데... 아닌 것 같다.

그래서 각 톱니바퀴를 돌렸을 때 일어나는 모든 과정을 각각의 함수로 만들었다.

첫번째 톱니바퀴라면 극성을 보고 이어서 2,3,4번째 톱니바퀴를 함수 내에서 돌리고

두번째 톱니바퀴라면 극성을 보고 1,3,번째 돌린 다음 3번의 극성을 보고 4번째 톱니바퀴를 돌리는 형식이다.

처음에는 쫙~~ 모든 코드를 나열해서 썼는데 제출하고 틀린 다음에 '너무 코드가 길고 중복되는 게 많네... 좀 합쳐야겠다!' 싶어서 톱니바퀴를 돌리는 함수는 따로 만들었다.

이제는 극성 체크만 하고 해당 함수를 호출하는 형식이다.

그래서 예제를 다 돌리고 통과한 다음 제출을 했는데 1퍼 컷!

 

...어째서 사정없이 컷이 당한건지 정신이 아득해질 때쯤 그냥 직접 쓰면서 해보기로 했다.

반례들을 열심히 찾으면서 하나하나 톱니바퀴를 손으로 돌렸다.

그랬더니 하나씩 나오더라

톱니바퀴를 반대로 돌리거나, 톱니바퀴 극성 위치를 이상한 걸로 체크한 케이스가 슉슉 나왔다.

이게 이전 걸로 갈 때는 현재의 9시와 이전의 3시를 비교하고, 다음 걸로 갈 때는 현재의 3시와 이전의 9시를 비교해야하는데 이게 코드로 가면 인덱스를 하나씩 빼야하기도 하고 현재를 움직인 다음 움직인 위치와 비교할 위치를 해야해서 쉽게 빠뜨려버렸던 거 같다.

손으로 반례 추적을 5번은 하고나서야 해결이 됐고 제출해서 통과를 받았다.

수많은 틀렸습니다

 

이전에 StringBuilder 사용에도 문제가 있었다.

나는 deleteCharAt의 반환값이 Char인줄 알았는데 해당 인덱스의 문자를 뺀 나머지 StringBuilder였다...?!

그래서 먼저 insert를 하고 deleteCharAt을 나중에하는 방식, 두 번에 나눠서 하는 방식으로 해결했다.

더 좋은 방법이 있을까...?

 

네 함수로 나눈 체크함수도 좀 합치고 싶은데 이게 내가 짠 코드에서는 쉽지 않아보인다...

 

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

import java.util.StringTokenizer

val gears: Array<StringBuilder> = Array(4) { StringBuilder() }
fun main() = with(System.`in`.bufferedReader()) {
    var answer = 0

    (0..3).forEach {
        gears[it].append(readln())
    }

    var k = readln().toInt()
    while (k-- > 0) {
        val st = StringTokenizer(readln())
        val num = st.nextToken().toInt()
        val dir = st.nextToken().toInt()

        when (num - 1) {
            0 -> checkOne(dir)
            1 -> checkTwo(dir)
            2 -> checkThree(dir)
            3 -> checkFour(dir)
        }
    }

    if (gears[0][0] - '0' == 1) answer += 1
    if (gears[1][0] - '0' == 1) answer += 2
    if (gears[2][0] - '0' == 1) answer += 4
    if (gears[3][0] - '0' == 1) answer += 8

    println(answer)
}

fun checkOne(dir: Int) {
    rotateGear(0, dir)

    if (gears[0][2 + dir] != gears[1][6]) {
        rotateGear(1, dir * -1)
    } else {
        return
    }

    if (gears[1][2 + dir * -1] != gears[2][6]) {
        rotateGear(2, dir)
    } else {
        return
    }

    if (gears[2][2 + dir] != gears[3][6]) {
        rotateGear(3, dir * -1)
    } else {
        return
    }
}

fun checkTwo(dir: Int) {
    rotateGear(1, dir)

    if (gears[1][6 + dir] != gears[0][2]) {
        rotateGear(0, dir * -1)
    }

    if (gears[1][2 + dir] != gears[2][6]) {
        rotateGear(2, dir * -1)
    } else {
        return
    }

    if (gears[2][2 + dir * -1] != gears[3][6]) {
        rotateGear(3, dir)
    } else {
        return
    }
}

fun checkThree(dir: Int) {
    rotateGear(2, dir)

    if (gears[2][2 + dir] != gears[3][6]) {
        rotateGear(3, dir * -1)
    }

    if (gears[2][6 + dir] != gears[1][2]) {
        rotateGear(1, dir * -1)
    } else {
        return
    }

    if (gears[1][6 + dir * -1] != gears[0][2]) {
        rotateGear(0, dir)
    } else {
        return
    }
}

fun checkFour(dir: Int) {
    rotateGear(3, dir)

    if (gears[3][6 + dir] != gears[2][2]) {
        rotateGear(2, dir * -1)
    } else {
        return
    }

    if (gears[2][6 + dir * -1] != gears[1][2]) {
        rotateGear(1, dir)
    } else {
        return
    }

    if (gears[1][6 + dir] != gears[0][2]) {
        rotateGear(0, dir * -1)
    } else {
        return
    }
}

fun rotateGear(idx: Int, dir: Int) {
    when (dir) {
        1 -> {
            gears[idx].insert(0, gears[idx][gears[idx].lastIndex])
            gears[idx].deleteCharAt(gears[idx].lastIndex)
        }
        -1 -> {
            gears[idx].append(gears[idx][0])
            gears[idx].deleteCharAt(0)
        }
    }
}