[Swift] 조이스틱 문제 풀이 [Programmers - Level2]

💬 문제

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

프로그래머스

 

---

• 처음엔 그리디 유형의 문제라고 해서 어떻게든 간단한 풀이방법을 찾아내려고 했습니다.
  그렇지만 최선의 결과를 도출하려면 이동의 경우의 수를 모두 파악하고 계산할 필요가 있었습니다.
  순간 재귀로 풀까 하는 생각이 들어서, 그리디로 풀이하는 힌트를 얻고자 질문하기에 들어갔는데 사람들이 화가 많이 나있었어요 ! ㅋㅋㅋㅋㅋㅠㅠㅠ 넘 공감...
• 질문하기를 살펴보니 그리디로는 최소 이동 횟수를 파악하기 힘든 문제였습니다. 따라서 dfs(재귀)를 이용해서 풀이해주었습니다.
  • 그리디로는 왼쪽, 오른쪽 둘다 이동하는 경우를 도출하기 어렵기 때문인 것 같아요. 그럼에도 그리디로 푸신 분들이 있더라고요 .. 존경스럽습니다,,!!

💬 Idea

1. 조이스틱을 상하로 이동시켜 알파벳을 만들어줄 때 알파벳별 최소 이동횟수를 미리 저장해준다.
   • 알파벳 O부터는 Z부터 거슬러올라가는 것이 더 빠르므로 Unicode.Scalar를 응용하여 A~N / O~Z 의 경우를 나누어서 최소 이동횟수를 abcDict에 저장해주었다.
2. 완성해야하는 name의 첫 번째 알파벳이 “A”가 아니라면 조이스틱으로 이동시켜 첫 번째 알파벳을 만들어준다.
3. 이후 첫 번째 커서 위치에서(0) dfs를 수행한다.
   • 오른쪽 으로 이동하여 도달할 수 있는 A가 아닌 알파벳을 찾아 dfs를 수행한다. (재귀)
   • 왼쪽 으로 이동하여 도달할 수 있는 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번 정답이 42인 이유가 궁금합니다.....

 

 

[테스트 7번 최소 이동로직]

JAANAAAAN (name)

AAAAAAAAA (initial)

 

1. 첫번째 알파벳 A -> J 로 변경    JAAAAAAAA (+9) 2. 인덱스 0에서 왼쪽으로 커서를 이동시켜 끝 인덱스에 위치한 N으로 이동 (+1)     A -> N 변경 (+13) 3. 마지막 인덱스에서 오른쪽으로 커서를 이동시켜 인덱스 3의 N으로 도달 (+4)     A -> N 변경 (+13)

 

= 9 + 1 + 13 + 4 + 13 = 40

 

제가 생각한 로직은 이러해서 40이 도출되었는데, 혹시 이상한 부분이 있다면 댓글로 알려주시면 감사하겠습니다..!!

 

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Programmers/level2/%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift