[Programmers/Kotlin] 조이스틱 (브루트포스 풀이, 오히려 빠르다?)

[도입]

  아마 프로그래머스에서 코딩테스트 준비해본 사람 중 이 문제 모르는 사람 없을 것 같다. 고득점 Kit 의 그리디 편에 수록된 문제이다. 나는 그리디로 풀려고 노력하다가 시간이 너무 오래걸려서 일단 브루트포스로 풀어보았다. (그리디 방법을 모색할 때마다 반례를 찾아서.. 그리디를 통과하는 코드를 찾아서 뭔지 묵혀두고 공부해야겠다.) 브루트포스로 이 문제를 푼다고했을 때, 이 문제의 핵심은 A가 아닌 모든 알파벳의 위치를 방문하는 최소의 움직임 수라고 생각한다. 왜냐하면 알파벳을 바꾸는 것은 +- 연산만으로도 충분하고 따로 작업할 수 있기 때문이다.

  이 문제 브루트포스로 풀면 시간초과 나지 않냐? 고 하시는 분을 위해 말씀드리자면 name 의 길이가 최대 20(N 이라 하자)이라 가능하다고 본다.  왼쪽 오른쪽 두 가지 경우를 문자열의 모든 문자마다 재귀하기 때문에 최대 2^N 번의 재귀. 여기서 그 매 재귀마다 name 의 길이 N 만큼이 검사하는데 필요하므로 시간복잡도 O(2^N * N) 이다.

  대입해보면 100만 * 20 이므로 대략 2000만이다. 1억에 한참 미치지 못하므로 브루트포스로도 충분히 풀만하다고 판단했다. 또한 가지치기만 제대로 하면 실질적으로 재귀하는 숫자는 훨신 적게 나올 것이라고 생각한다.

  문제 설명을 대충 해보자면, 게임방가서 기록을 세웠으면 자기 이름 이니셜 남긴 기억이 다들 있을텐데 그거 최소횟수 찾는 문제이다. 자세한 설명은 아래 그림을 확인한다.

 

[풀이 과정]

알파벳 전체 변환 비용을 전처리로 계산해놓고

브루트포스로 최단 이동 비용 을 구해서 알파벳 전체 변환 비용에 더해줘서 답을 낸다.

 

여기서 주의할 점은 방문해야할 곳(A 가 아닌 곳)을 모두 방문했는지, 즉 min 정답의 후보인지 체크하는 배열을 글로벌 변수로 만들면 안된다. 왜냐하면 왼쪽 오른쪽을 여러번 반복한 경우에 이미 방문한 곳이 방문하지 않은 것처럼 변할 수 있기 때문이다. 아래 코드처럼 각 스택프레임에 로컬로 배열을 잡아두어야 모든 테스트케이스가 통과한다.

 

아래 주석과 함께 코드를 참고바랍니당.

class Solution {
    private var min = Int.MAX_VALUE
    private var gName = ""
    fun solution(name: String): Int {
        gName = name
        var answer = 0

        // 전처리
        val check = Array(name.length) { false }
        for (i in name.indices) {
            if (name[i] == 'A') check[i] = true
            if (name[i] > 'M') answer += ('Z' - name[i] + 1) else answer += (name[i] - 'A')
        }

        // 브루트 포스
        bruteforce(0, 0, check)

        // 최소 이동값 더해주기
        answer += min

        return answer
    }
    private fun bruteforce(cur: Int, dist: Int, check: Array<Boolean>) {
        // min 보다 같거나 높다면 더이상 검사할 필요도 없다.
        if (dist >= min) return

        // 왼오왼오왼 같은 경우에 방문했음에도 방문하지 않은 것처럼 되는 것을 방지하기 위해 매번 새롭게 생성해준다.
        val nextCheck = check.copyOf()

        // 정답이 될 수 있는지 체크
        nextCheck[cur] = true
        var all = true
        for (i in nextCheck.indices) {
            if (!nextCheck[i]) all = false
        }
        // 정답이라면 갱신 시도
        if (all && min > dist) min = dist

        // 양방향 각각 재귀로 시도
        if (cur >= gName.length - 1) bruteforce(0, dist + 1, nextCheck) else bruteforce(cur + 1, dist + 1,nextCheck)
        if (cur <= 0) bruteforce(gName.length - 1, dist + 1, nextCheck) else bruteforce(cur - 1, dist + 1, nextCheck)
    }
}

 
[재밌는 점]

다른 사람의 그리디 풀이를 보며 비교해 봤는데 이 문제는 대부분의 경우에 의외로 브루트포스가 더 빠른 것 같다?? 왜 그런지는 더 공부해봐야 알 것 같다. 

이상 그리디 감잡으려다가 브루트포스 감잡은 글..