[프로그래머스] 조이스틱 / Swift

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

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

[문제 보기]

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

 

▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

name, return

"JEROEN"	56
"JAN"	23

---

풀이 과정

1. 입력받은 문자열을 순회하면서 A가 아닌 원소들을 담은 배열 comp을 만든다.

ex) ABCDF => comp: [B,C,D,F]

 

2. 상하 방향 횟수 계산을 위해 A-Z 구간에 각각 해당하는 필요 조작 수를 미리 계산해 둔 딕셔너리 배열을 만들어둔다. ( 코드에서는 alphabet 배열에 해당함 )

 

3. 반복문 안에서 사용되는 left와 right는 comp 배열에서 효율적으로 탐색하기 위해 사용되는 현재까지 탐색한 위치 저장 변수이다.

 

4. comp 배열내에 있는 원소들을 비교해 가면서 현재 상태에서 다음 번째까지 최소 조작 수를 요구하는 선택만을 해가며 반복한다. 구체적으로는 아래와 같은 선택을 반복하며 계산한다.

1. 다음 이동할 수 있는 위치의 리스트를 가져온다. 가져오게 될 후보들은 현재 위치에서 왼쪽방향으로 이동했을때 만나는 원소와 오른쪽 방향으로 이동했을 때 만나는 원소에 해당한다. 이 과정에서 같은 원소를 선택하게 될 경우도 있다.
2. 현재 위치에서 선택된 후보들 까지의 이동 비용을 계산한다.
3. 계산한 비용 중 적은 비용이 발생하는 위치를 다음 이동할 위치로 지정한다.

5. 반복문이 작동하기 위한 조건은 현재 시작된 위치부터 A가 아니라서 계산되어야 할 위치라는 것이다. ( 즉, current는 입력받은 string에 대한 위치가 아니라 A가 아닌 원소들을 모아둔 comp 배열에서의 위치이어야 한다는 것 ) 그러므로 만약 입력받은 string이 A부터 시작되는 문자열이라면 comp에 들어가는 첫번째 원소는 string의 첫번째 원소가 아니므로, 반복문에 진입하기 전에 current와 left, right의 위치를 잡아주어야 한다.

 

import Foundation

var comp = [Int]()
var alphabet = [Character: Int]()

// right는 마지막 원소의 다음 인덱스, 여기서 반환되는 인덱스는 comp의 인덱스
func getLeftItemIndex(left: Int, right: Int, current: Int) -> Int {
    let length = right - left
    return (length + (current - left) - 1) % length + left
}

func getRightItemIndex(left: Int, right: Int, current: Int) -> Int {
    let length = right - left
    return (length + (current - left) + 1) % length + left
}

func getMinCost(_ originLength: Int, from: Int, to: Int) -> Int {
    let inner = abs(comp[from] - comp[to])
    let outer = originLength - inner
    return min(inner, outer)
}

func solution(_ name:String) -> Int {
    let nameArr = Array(name)
    for (i, element) in name.enumerated() {
        if element != "A" {
            comp.append(i)
        }
    }
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ".enumerated().forEach {
        let i = $0.offset
        alphabet[$0.element] = min(i, 26 - i)
    }
    
    
    var left = comp.startIndex, right = comp.endIndex
    // 시작할 위치 조정
    var current = 0, cost = 0
    if let firstItemIdx = comp.first, let lastItemIdx = comp.last {
        let d1 = firstItemIdx
        let d2 = nameArr.count - lastItemIdx
        if d1 > d2 {
            current = right - 1
            cost += d2
        } else {
            current = left
            cost += d1
        }
    }
    
    while left < right {
        // 현재 위치의 글자를 바꾸는 비용 계산
        cost += (alphabet[nameArr[comp[current]]] ?? 0)
        
        // 다음 이동에 필요한 비용 계산
        let lt = getLeftItemIndex(left: left, right: right, current: current)
        let rt = getRightItemIndex(left: left, right: right, current: current)
        let lcost = getMinCost(nameArr.count, from: current, to: lt)
        let rcost = getMinCost(nameArr.count, from: current, to: rt)
        
        if current == left {
            left += 1
        } else {
            right -= 1
        }
        
        // cost를 비교
        if lcost < rcost {
            current = lt
            cost += lcost
        } else { // 둘이 같은 경우도 존재
            current = rt
            cost += rcost
        }
    }
    return cost
}

 

어렵게 풀기도해서 다른 사람 풀이 블로그들을 보던 중에, 이 문제의 테스트케이스가 오류가 있는 것 같다는 글을 보았다.

BBBBAAAB 로 입력받으면 실제 최소값은 시작할때 오른쪽 끝에 한번 방문하고 다시 원점으로 되돌아와서 오른쪽으로 가는 방법으로 10이 정답이지만, (내가 구현한 방식으로 포함한) 한 케이스마다의 최적의 방향으로 계산했을 때 나오는 결과값 12로도 통과가 되었기 때문에 오류라는 내용이었다.

 

내가 구현한 코드에서는 그리디의 방식으로 현재 위치에서, 다음번 원소에 대해서만 최적의 값을 계산하게되는데 비용이 동등할 때는 오른쪽으로 진행하게 구현되어있어 12가 나온다.

 

한 선택이 전체 값에 대해 항상 최선의 시나리오로 움직이는지 판단해야하는데 이 문제의 경우에서 최적의 해를 구하려면 한번에 모든 경우의 계산해야 하는 방향으로 구현해야하는 것 같았다.

나중에 다시풀어보아야겠다.