[프로그래머스] 조이스틱 (Kotlin)

문제

https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

 

풀이

0. 문제 해석

그리디 알고리즘으로 분류되어있는 문제인데

개인적으로 브루트포스 알고리즘으로 분류하는 게 나을 것 같은 문제이다.

 

우선, 위아래 조작의 경우 좌우 조작의 순서에 영향을 받지 않으므로

미리 구할 수 있다.

위로 14번 이상 조작해야 하는 경우 알파벳이 26개이므로 밑으로 조작하는 것이 더 빠르다.

위와 같은 방식으로 한글자씩 위아래 조작 횟수를 누적시켜놓는다.

또한 이미 바꿨다는 표시를 하기 위한 visit 배열을 하나 선언한다. (이미 A라면 바꿀 필요가 없으므로 계산 과정에서 true)

 

이제 그 누적값에 좌우 조작 횟수만 더해주면 되는데

각각의 위치에서 왼쪽방향, 오른쪽방향 탐색을 진행하면서 탐색이 끝난 경우 리턴하여 최소 이동경로를 찾으면 된다.

 

하지만 한쪽방향으로만 이동하는 것이 아니라 좌우 방향을 바꾸는 경우가 이득인 경우도 있으므로 잘 탐색해야 한다.

 

단 여기서 항상 최적해를 찾는 그리디 방식으로 하면 문제가 발생하는데

예를 들어

 

1. "ABCDAA"

2. "ABCDAB"

3. "BBBBAAAABA"

 

위와 같은 케이스의 경우

1번 케이스는

시작점에서 오른쪽으로 1칸 가면 A가 아닌 문자가 있고,

왼쪽으로 3칸 가야 A가 아닌 문자가 있으므로 상관없고

 

2번 케이스의 경우엔

시작점에서 오른쪽으로 1칸 가면 A가 아닌 문자가 있고,

왼쪽으로도 1칸 가야 A가 아닌 문자가 있으므로 이 경우는 둘다 탐색하도록 하면 되는데,

 

3번 케이스의 경우엔

시작점에서 오른쪽으로 1칸 가면 A가 아닌 문자가 있고,

왼쪽으로는 2칸 가야 A가 아닌 문자가 있으므로 그리디 방식이라면 처음에 무조건 오른쪽으로 이동할 것이다.

 

하지만 잘보면 최소이동경로는

왼쪽 2번 이동하여 B 변경,

오른쪽 5번 이동하여 나머지 B 다 변경으로

 

그리디의 경우와 다른 것을 알 수 있다.

 

따라서 전체탐색으로 해결해야 한다.

1. 전체 코드

// [프로그래머스] 조이스틱 (Kotlin)
import kotlin.math.*

class Solution {
    var len = 0
    var min = Integer.MAX_VALUE
    lateinit var visit : Array<Boolean> // 변경된 값 => true
    var sum = 0 // 다 변경됐는지 체크

    fun solution(name: String): Int {
        var answer = 0 
        len = name.length
        visit = Array(len) { false }
        
        // 처음 자리는 좌우 이동 필요 X
        sum = len - 1
        visit[0] = true

        // 조이스틱 위아래 조작 합계
        for(i in 0 until len){
            var n = name[i] - 'A'

            // 14보다 큰 경우 아래로 조작
            if(n >= 14){
                n = 26 - n
            }
            answer += n

            // 조작 필요없는 곳 (A)
            if(n == 0){
                visit[i] = true
                if(i != 0) {
                    sum--
                }
            }
        }

        solve(0,0,0)
        answer += min
        return answer
    }

    fun solve(i: Int, res: Int, count: Int){

        // 다 변경 완료 시 좌우 이동 횟수 출력
        if(count == sum){
            min = min(min,res)
            return
        }
        var left = i
        var right = i
        var lCount = 0
        var rCount = 0

        while(lCount < len){
            left--
            lCount++

            // 첫 번째 위치에서 왼쪽으로 이동
            if(left < 0){
                left = len - 1
            }
            // 아직 변경되지 않은 자리 만나면 break
            if(!visit[left]){
                break
            }
        }

        while(rCount < len){
            right++
            rCount++

            // 마지막 위치에서 오른쪽으로 이동
            if(right >= len){
                right = 0
            }
            // 아직 변경되지 않은 자리 만나면 break
            if(!visit[right]){
                break
            }
        }

        visit[right] = true
        solve(right, res + rCount, count + 1)
        visit[right] = false
        visit[left] = true
        solve(left, res + lCount, count + 1)
        visit[left] = false
    }
}