[Algorithm] 프로그래머스 : 조이스틱

프로그래머스 lv2 : 조이스틱

코드

import Foundation

func solution(_ name:String) -> Int {
    var distance: [Int] = [Int]()
    var curCount: Int = 0
    var curIndex: Int = 0
    for nameIndex in 0..<name.count {
        distance.append(getDistance(target: Array(name)[nameIndex]))
    }

    while distance.reduce(0, +) != 0 {
        let info: (distance: Int, index: Int) = getNextIndex(curIndex: curIndex, arr: distance)
        curIndex = info.index
        curCount += info.distance + distance[curIndex]
        distance[curIndex] = 0
    }

    return curCount
}

func getDistance(target: Character) -> Int {
    if Int(target.asciiValue!) - 65 > 13 {
        return 91 - Int(target.asciiValue!)
    } else {
        return Int(target.asciiValue!) - 65
    }
}

func getNextIndex(curIndex: Int, arr: [Int]) -> (distance: Int, index: Int){
    if arr[curIndex] != 0 {
        return (0, curIndex)
    }
    
    var leftIndex: Int = curIndex - 1
    var rightIndex: Int = curIndex + 1
    var count: Int = 0
    let length: Int = arr.count
    while true {
        count += 1
        leftIndex = leftIndex == -1 ? length - 1 : leftIndex
        rightIndex = rightIndex == length ? 0 : rightIndex
        
        if arr[rightIndex] != 0 {
            return (count, rightIndex)
        } else if arr[leftIndex] != 0 {
            return (count, leftIndex)
        }
        
        leftIndex -= 1
        rightIndex += 1
    }
}

풀이과정

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 해야한다.
또한 단어는 모두 A로 이루어져 있다. 예를들어 JAZ라는 이름을 만들고 싶다면, AAA 에서 시작하는 것이다. 또한 이름 맨 왼쪽에서 한번 더 왼쪽으로 가면 이름의 맨 마지막으로 조이스틱 커서가 옮겨지고, 이는 맨 오른쪽도 마찬가지로 맨 처음으로 옮겨진다. 또한 A에서 조이스틱을 위로 조작하면 Z가 되고 Z에서 조이스틱을 아래로 조작하면 A가 된다.

나는 먼저 각 글자별로 움직여야하는 조작횟수를 담은 distance 배열을 초기화 해줬다. getDistance메소드를 구현하였는데, 아스키 코드값을 비교하였다. A에서 만들어야하는 Character 아스키밸류를 뺀 값이 13보다 크다면 오른쪽이 아닌 왼쪽으로 찾게 했다. 즉 JAZ에 대한 distance 배열을 만들어 보자면 [9, 0, 1] 이 될것이다.

그 다음은 이제 바꿀 문자를 찾아야한다. getNextIndex 메소드를 구현하였는데, 문자열의 0번째 인덱스부터 시작해서, 만약 0번쨰 인덱스의 distance가 0이 아닐 경우는 조이스틱을 좌우로 움직일 필요가 없다. 그리고 sum에 해당 distance를 더해주고, distance를 0으로 바꿔준다. 위 JAZ로 예시를 들어보자면 [0, 0 ,1]이 되고 sum은 9가 될 것이다. 그 다음 양 옆으로 인덱스를 뻗어가면서 최소 변경하는 문자를 찾아준다. 그리고 원래 인덱스에서 최소 변경 인덱스의 거리와 최소 변경 디스턴스를 리턴한다. 만약 위 값이 같다면, 오른쪽을 먼저 고려해주도록 했다. 그런데 이 경우 왼쪽을 먼저 고려해도 값이 같아야하는데 왼쪽을 먼저 고려할 경우 테스트 케이스를 통과하지 못해서 오른쪽을 먼저 고려하게 하였더니 통과하더라. 그리고 해당 디스턴스를 sum에 더하고 0 으로 만들어 준다.
이 모든 과정을 distance 배열의 합이 0이 될때까지 반복해준다. distance의 합이 0이라는 것은 더 이상 바꿀 문자열이 없다는 것이다.

느낀 점

왜 바꿔야할 값이 같을 때 왼쪽을 선택하느냐, 오른쪽을 선택하느냐가 정답에 영향을 주는지 모르겠다. 말그대로 그리디 알고리즘이란 매 순간마다 최적해를 찾아내는 것으로 알고있기 때문이다. 차라리 제약사항을 줬더라면 해결하는데 시간이 덜 걸렸을텐데 참 어렵다.