[고득점 Kit (탐욕법)] 조이스틱 (Swift, Python)

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

 

풀이

 먼저 각 알파벳 별로 A에서 최소 몇 번의 조이스틱 조작으로 해당 알파벳에 도달할 수 있는지를 배열로 만들어줬다. N은 위쪽 아래쪽 모두 13번을 조작해야하고 A에서 N까지는 위쪽으로, N 이후부터는 아래쪽으로 움직이면 최소한의 조작 횟수를 구할 수 있다.

 

 그렇게 입력으로 주어진 name의 각각의 알파벳을 몇 번 움직여야 하는지 구한다. A가 아닐 경우에는 조이스틱 조작이 필요한 인덱스 배열(changeIdx)에 담아둔다. 그 후 changeIdx의 원소가 모두 없어질 때까지 while문을 통해 다음을 반복한다.

 

1. 현재 위치(current)를 기준으로 왼쪽으로 이동했을 때 가장 먼저 마주치는 인덱스 번호와 오른쪽으로 이동했을 때 가장 먼저 마주치는 인덱스 번호를 구한다.
2. 둘 중 어떤 인덱스가 현재 위치에서 더 가까운지 판단하여 이동 횟수를 answer에 카운트해준다.
3. 이제 현재 위치를 둘 중 하나로 갱신하여 위의 과정을 반복한다.

 매 번 커서를 옮길 때마다 최선의 선택을 하기 때문에 탐욕법에 해당하는 것 같다.

 

코드

[Swift]

import Foundation

var alphaMove: [Int] = [] // 각각의 알파벳별로 A에서 몇 번의 조이스틱 조작으로 만들 수 있는지를 담아주는 배열
var changeIdx: [Int] = [] // 조이스틱 조작으로 알파벳 변경이 필요한 인덱스를 담아주는 배열
var tmp: Int = 2

func solution(_ name:String) -> Int {
    var answer: Int = 0
    var current: Int = 0
    
    // N을 기준으로 조이스틱 조작 횟수를 담아준다.  ....., 10, 11, 12, 13(N), 12, 11, 10, ....
    for i in 0..<26 {
        if i <= 13 {
            alphaMove.append(i)
        } else {
            alphaMove.append(i - tmp)
            tmp += 2
        }
    }
    
    // 입력으로 주어진 name의 알파벳별로 필요한 조이스틱 조작 횟수를 카운트하고
    // 조이스틱 조작이 필요한 인덱스를 changeIdx에 담아준다.
    for i in 0..<name.count {
        let ch: Character = name[name.index(name.startIndex, offsetBy: i)]
        let moveCnt: Int = alphaMove[Int(ch.asciiValue!) - 65]
        answer += moveCnt
        if moveCnt != 0 && i != 0 {
            changeIdx.append(i)
        }
    }
    
    // 현재 커서의 위치(current)에서 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때 먼저 마주치는 인덱스를 구해서
    // 왼쪽 이동과 오른쪽 이동중에 어떤 것이 최소가 되는지를 구한다.
    // 최소가 되는 쪽으로 이동하고 이를 계속 반복한다.
    while !changeIdx.isEmpty {
        let left: Int = changeIdx[changeIdx.count - 1]
        let right: Int = changeIdx[0]
        
        var leftMove: Int = 0, rightMove: Int = 0
        
        if current > left {
            leftMove = current - left
        } else {
            leftMove = current + name.count - left
        }
        
        if current > right{
            rightMove = right + name.count - current
        }
        else{
            rightMove = right - current
        }
        
        if leftMove < rightMove {
            answer += leftMove
            current = left
            changeIdx.removeLast()
        } else {
            answer += rightMove
            current = right
            changeIdx.removeFirst()
        }
    }

    return answer
}

[Python]

alphaMove = [i for i in range(14)] + [i for i in range(12, 0, -1)] # 각각의 알파벳별로 A에서 몇 번의 조이스틱 조작으로 만들 수 있는지를 담아주는 배열
changeIdx = [] # 조이스틱 조작으로 알파벳 변경이 필요한 인덱스를 담아주는 배열


def solution(name):
    answer = 0
    current = 0

    # 입력으로 주어진 name의 알파벳별로 필요한 조이스틱 조작 횟수를 카운트하고
    # 조이스틱 조작이 필요한 인덱스를 changeIdx에 담아준다.
    for i in range(len(name)):
        moveCnt = alphaMove[ord(name[i]) - 65]
        answer += moveCnt

        if moveCnt != 0 and i != 0:
            changeIdx.append(i)

    # 현재 커서의 위치(current)에서 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때 먼저 마주치는 인덱스를 구해서
    # 왼쪽 이동과 오른쪽 이동중에 어떤 것이 최소가 되는지를 구한다.
    # 최소가 되는 쪽으로 이동하고 이를 계속 반복한다.
    while changeIdx:
        left, right = changeIdx[-1], changeIdx[0]

        if current > left:
            leftMove = current - left
        else:
            leftMove = current + len(name) - left

        if current > right:
            rightMove = right + len(name) - current
        else:
            rightMove = right - current

        if leftMove < rightMove:
            answer += leftMove
            current = left
            changeIdx.pop()
        else:
            answer += rightMove
            current = right
            changeIdx.pop(0)

    return answer