[Algorithm] 조이스틱

[hwangJi-dev]

💬 문제

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

💬 Idea

• 처음엔 그리디 유형의 문제라고 해서 어떻게든 간단한 풀이방법을 찾아내려고 했다.
  그렇지만 최선의 결과를 도출하려면 이동의 경우의 수를 모두 파악하고 계산할 필요가 있었다.
  순간 DFS로 풀까 하는 생각이 들어서, 그리디로 풀이하는 힌트를 얻고자 질문하기에 들어갔는데 사람들이 화가 많이 나있었다 ! ㅋㅋㅋㅋㅋ (너무 동감...)
• 질문하기를 살펴보니 그리디로는 최소 이동 횟수를 파악하기 힘든 문제였다. 따라서 dfs(재귀)를 이용해서 풀이해주었다.
  • 아마 테스트 케이스가 추가되고서 기존의 문제 색을 잃은 것 같다.

1. 조이스틱을 상하로 이동시켜 알파벳을 만들어줄 때 알파벳별 최소 이동횟수를 미리 저장해준다.
   1. 알파벳 O부터는 Z부터 거슬러올라가는 것이 더 빠르므로 Unicode.Scalar를 응용하여 AN / OZ 의 경우를 나누어서 최소 이동횟수를 abcDict에 저장해주었다.
2. 완성해야하는 name의 첫 번째 알파벳이 “A”가 아니라면 조이스틱으로 이동시켜 첫 번째 알파벳을 만들어준다.
3. 이후 첫 번째 커서 위치에서(0) dfs를 수행한다.
   1. 오른쪽 으로 이동하여 도달할 수 있는 A가 아닌 알파벳을 찾아 dfs를 수행한다. (재귀)
   2. 왼쪽 으로 이동하여 도달할 수 있는 A가 아닌 알파벳을 찾아 dfs를 수행한다. (재귀)
4. 이렇게 오른쪽, 왼쪽 모두 이동하며 얻게 되는 최소 카운트를 res에 저장하고 함수를 종료한다.
5. 결과를 도출할 때 첫 번째 알파벳을 만들어주기 위해 이동시켰던 횟수만큼을 더해준다.

💬 풀이

import Foundation

func solution(name:String) -> Int {
    var abcDict: [String: Int] = [:]
    let name = name.map({ String($0) })
    var initialName = Array(repeating: "A", count: name.count)
    var res = Int.max
    
    for i in 1...26 {
        if let scalar = Unicode.Scalar(64 + i) {
            if i <= 14 {
                abcDict[scalar.description] = i - 1
            } else {
                abcDict[scalar.description] = abs(i - 26) + 1
            }
        }
    }
    //"A": 0, B": 1, "C": 2, "D": 3, "E": 4, "F": 5, "G": 6, "H": 7, "I": 8, "J": 9, "K": 10, "L": 11, "M": 12, "N": 13, "O": 12, "P": 11, "Q": 10, "R": 9, "S": 8, "T": 7, "U": 6, "V": 5, "W": 4, "X": 3, "Y": 2, "Z": 1
    
    if name[0] != "A" {
        initialName[0] = name[0]
    }
    
    /// dfs
    func dfs(_ initialName: [String], _ count: Int, _ cursor: Int) {
        if initialName == name {
            res = min(res, count)
            return
        }
        
        // right
        let right = joystickMovesLeftorRight(true, cursor, name, initialName)
        var rightName = initialName
        var rightCount = count
        rightName[right[0]] = name[right[0]]
        rightCount += abcDict[name[right[0]]]! + right[1]
        dfs(rightName, rightCount, right[0])
        
        // left
        let left = joystickMovesLeftorRight(false, cursor, name, initialName)
        var leftName = initialName
        var leftCount = count
        leftName[left[0]] = name[left[0]]
        leftCount += abcDict[name[left[0]]]! + left[1]
        dfs(leftName, leftCount, left[0])
    }
    
    dfs(initialName, 0, 0)
    return name[0] != "A" ? res + abcDict[name[0]]! : res
}

// MARK: - 조이스틱 좌/우로 이동 후 커서와 이동횟수를 반환하는 메서드
func joystickMovesLeftorRight(_ isRight: Bool, _ cursor: Int, _ name: [String], _ initialName: [String]) -> [Int] {
    var cursor = cursor
    var moves = 0
    
    for _ in name {
        cursor = isRight ? cursor + 1 : cursor - 1 // 오른쪽으로 커서 이동시 + 1 / 왼쪽으로 커서 이동시 - 1
        moves += 1 // 이동횟수는 어떤 경우든 + 1
        
        if cursor > name.count - 1 {
            cursor = 0
        }
        
        if cursor < 0 {
            cursor = name.count - 1
        }
        
				// 찾아야하는 알파벳: A가 아니면서 아직 변환되지 않은 것
        if name[cursor] != "A" && initialName[cursor] == "A" {
            break
        }
    }
    
    return [cursor, moves]
}


근데.. 테스트케이스 7번은 실패가 떴다 ! 40이 최소횟수가 아닌가…? 기댓값이 왜 더 크지 😅😅 함수 설계 잘못했나 아찔했다..
이게 실패해서 공책에다 테스트케이스 직접 계산해봤는데,, 최소가 40이 맞다..! 그래서 그냥 제출을 해보았다.

이게 웬걸..? ㅋㅋㅋㅋㅋ 맞았다.. 게다가 이 문제 7점이나 주네..!