[문제풀이]프로그래머스-조이스틱

seongwonchung·2021년 1월 11일

문제설명

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

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

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

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

첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.

조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.

마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

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

제한사항

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

해설

이 문제는 그리디 알고리즘 카테고리에 속해 있고, 최소 이동횟수를 구하는 문제이다. 이동하는 경우는 상하로 알파벳 변경 하는 경우와 좌우로 커서이동하는 경우 두 가지가 독립적이기 때문에 나누어서 생각하였다.

상하로 알파벳 변경(topDown)의 경우, ascii 코드를 활용하였다. 시작점인 'A'와 마지막인 Z는 각각 65, 90의 값을 갖는다. 따라서 name의 글자와의 거리를 아스키 코드의 차이값으로 각각 계산하여 최솟값을 알파벳을 변경하는 최소 횟수로 하였다.

좌우로 커서이동(leftRight)의 경우가 꽤 까다로웠다. 우선 오른쪽/왼쪽으로 이동하는 경우를 나누어 생각하였다. 또, wordToChange를 따로 두어서 name과 비교하도록 했다. 오른쪽/왼쪽으로 이동하면서, wordToChange와 name의 해당 인덱스의 글자가 다를 경우, 변경해야하는 지점이므로 해당 인덱스까지의 거리가 moveR/moveL이 된다.

인덱스를 구할 때는 오른쪽의 경우 인덱스 범위를 넘어가면 len(name)을 빼주고, 왼쪽의 경우 len(name)을 더해줘서 0 ~ len(name)-1의 인덱스 범위내에 있도록 했다.

그리고 moveR과 moveL을 비교하여 이동횟수가 적은 쪽으로 이동하게 했다.

이 때, 이동횟수가 같을 경우 오른쪽으로 이동하게 했는데, 이렇게 풀어야 테스트케이스 11번이 통과되는 듯 하다. 하지만, "BBBAAAAB"같은 경우 왼쪽으로 먼저 이동하는 것이 최소이동 횟수가 된다. 따라서 아래 코드로는 이러한 테스트케이스에서 오답일 수 있을 것 같다. 아마 문제의 제한사항에서 마지막 글자에서 첫 글자로 이동할 수 있다는 조건이 없기 때문에 답이 이렇게 되는것 같기도 하고.. 찾아봐도 논란이 조금 있는 것 같다.

그리고 마지막으로 첫번째 시작점의 경우, leftRight에서 무조건 한칸씩 움직인 다음부터 고려하기 때문에 wordToChange에서 변경해준 후에 이동횟수 계산 + 단어 변경 을 했다.

코드

def solution(name):
    def topDown(answer,c):
        answer += min((ord(c) - 65, 90-ord(c)+1))
        return answer
    def leftRight(wordToChange, name, i):
        moveR=1
        moveL=1
        #right
        while True:            
            if i+moveR > len(name)-1:
                indexR = i+moveR - len(name)
            else: 
                indexR = i+moveR
            if wordToChange[indexR] != name[indexR]:
                break
            moveR+=1
        #left
        while True:            
            if i-moveL < 0:
                indexL = i-moveL + len(name)
            else: 
                indexL = i-moveL
            if wordToChange[indexL] != name[indexL]:
                break
            moveL+=1
        
        if moveR <= moveL:
            return moveR, indexR
        else:
            return moveL, indexL
        
    answer = 0
    cursor = 0
    wordToChange = ['A']*len(name)
    name=list(name)
    #topDown
    for c in name:
        answer = topDown(answer, c)
    #leftRight
    while wordToChange != name:
        #change first letter
        wordToChange[cursor] = name[cursor]
        #start move
        move, cursor = leftRight(wordToChange, name, cursor)
        wordToChange[cursor] = name[cursor]
        answer+= move
    return answer