[알고리즘 연습] 조이스틱 (프로그래머스 lv2, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/42860?language=swift

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

풀이

import Foundation

func solution(_ name:String) -> Int {
    let name = Array(name)
    let aValue = Int(Character("A").asciiValue!)
    let zValue = Int(Character("Z").asciiValue!)

    // 1
    var updown = 0    
    var leftright = name.count-1  

    for startIdx in 0..<name.count {
        // 2
        updown += min(Int(name[startIdx].asciiValue!) - aValue, zValue - Int(name[startIdx].asciiValue!) + 1)

        // 3
        var endIdx = startIdx + 1
        while endIdx < name.count && name[endIdx] == "A" {
            endIdx += 1
        }

        // 4
        let moveFront = startIdx * 2 + (name.count - endIdx)
        let moveBack = (name.count - endIdx) * 2 + startIdx

        // 5
        leftright = min(leftright, moveFront)
        leftright = min(leftright, moveBack)
    }

    // 6
    return updown + leftright
}

예전에 Python으로 풀었던 문제인데, 테스트 케이스가 추가되면서 같은 로직으로는 풀리지 않았습니다. (2022.01.14 기준 추가) 풀이의 핵심은 특정 index 기준에서 다시 돌아가는 경우들을 생각하고 이를 단순히 처음부터 끝까지 접근하는 경우와 비교하는 거예요. 중간에 "A"가 매우 많을 경우 다시 돌아가는 것이 더 나을 수 있기 때문이죠.

1

    // 1
    var updown = 0    
    var leftright = name.count-1

• 먼저 문자를 변경하는 updown과 위치를 변경하는 leftright를 나누어 생각합니다. updown은 모든 문자가 "A"일 경우 0일수도 있기 때문에 초기값을 0으로 주었습니다. leftright는 가장 기본적인 이동으로 왼쪽에서 오른쪽으로 쭉 이동할 경우 name.count-1만큼 이동할 것이므로 이를 초기값으로 설정했습니다.

2

        // 2
        updown += min(Int(name[startIdx].asciiValue!) - aValue, zValue - Int(name[startIdx].asciiValue!) + 1)

• updown의 이동은 어차피 꼭 해야되는 것이니 각 문자마다 무조건 처리해주면 됩니다. (아스키코드 활용)

3

        // 3
        var endIdx = startIdx + 1
        while endIdx < name.count && name[endIdx] == "A" {
            endIdx += 1
        }

• 현재 index인 startIdx의 문자 다음 문자에 얼마나 연속된 A가 존재하는지 확인합니다. 그리고 그 A가 끝나는 지점을 endIdx라고 하고 계산합니다. 결과적으로는 위와 같은 형태로 startIdx, endIdx가 구해질 거예요.

4

        // 4
        let moveFront = startIdx * 2 + (name.count - endIdx)
        let moveBack = (name.count - endIdx) * 2 + startIdx

• 문제의 핵심입니다. 중간에 "A"들이 매우 많으면 다시 돌아가고, 이 경우를 가장 기본적인 이동(왼쪽에서 오른쪽으로 쭉 이동하는 경우)과 비교해 더 빠른 방법을 찾습니다. 우리는 앞서 startIdx와 endIdx를 구해놨으니 이를 통해 2가지 경우를 계산해봅시다.

• 먼저 해당 startIdx를 먼저 찍고 endIdx로 돌아가는 경우입니다. 이 경우 이동 횟수는 startIdx * 2 + (name.count - endIdx)가 될 것입니다.

• 다음으로 endIdx를 먼저찍고 startIdx로 돌아가는 경우입니다. 이 경우 이동횟수는 (name.count - endIdx) * 2 + startIdx가 되겠죠?

5

        // 5
        leftright = min(leftright, moveFront)
        leftright = min(leftright, moveBack)

• 이제 필요한 케이스들의 이동 횟수를 모두 구했으니 이 중 가장 작은 경우를 찾아 leftright에 반복 적용해줍니다.

6

    // 6
    return updown + leftright

• 결과는 이렇게 구한 leftright와 updown을 더해주면 됩니다.

생각보다 이해하기 어려워서 처음으로 알고리즘 문제에 시각자료도 만들어봤네요...😂

우연히 제 블로그에 오신 분과 까먹고 또 찾아볼 미래의 저 모두 쉽게 이해되길 바랍니다. 🙇🏻‍♂️