[프로그래머스] 조이스틱 - Python

 

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

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

 

---

풀이

크게 두 가지 방향에서 최솟값을 고려해야 한다.

 

 

첫 번째로는 상, 하 방향의 관점이다. A부터 오름차순으로 알파벳을 찾는 것이 빠른지, 아니면 Z부터 내림차순으로 찾는 것이 빠른지 비교를 한다. 문자열에 속한 알파벳들을 차례로 탐색하여 최솟값을 찾아 answer에 더해 나간다. 해당 문자가 A인 경우는 0, Z인 경우는 1임을 주의한다.

for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)

 

두 번째로 좌, 우 방향의 관점이다. 문제에서 A로만 이루어진 상태에서 문자열을 찾는 것이기 때문에 마지막에 남은 문자열들이 연속된 A로 이루어져 있다면 이동하지 않고 문자열을 완성시킬 수 있게 된다. 때문에 왼쪽에서 오른쪽으로만 이동하는 일반적인 경우의 움직이는 횟수와 반대 방향으로 이동하는 경우의 움직이는 횟수를 비교하여 최솟값을 찾는다.

 

이해를 돕기 위해 아래 그림을 보자. "BBBAABB"라는 문자열을 입력 받은 경우이다.

파란색 화살표 대로 왼쪽에서 오른쪽으로만 이동하는 경우는 문자열 길이에서 1을 뺀만큼 이동하게 된다. 따라서 이 경우는 값이 7이 된다.

 

빨간색 화살표 대로 이동하는 경우를 생각해 보자.

- 우선 A가 나오기 전까지 왼쪽에서 오른쪽으로 이동(①)하다가 A를 마주치면 온만큼 되돌아 간다(②).

- 그다음 문자열의 끝으로 돌아서 A가 나오기 전까지 이동한다(③).

이러한 이동을 하는 경우는 값이 2 + 2 + 2 = 6이 된다.

 

이 과정을 통해 얻게된 최소 이동 값을 마찬가지로 answer에 더하게 되면 최종 결과를 도출해 낼 수 있다.

 

이 과정을 코드로 옮기면 다음과 같다.

        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        min_move = min(min_move, i + i + len(name) - next)

 

해당 코드는 첫 번째 방향의 for문 안에서 동작한다. while문을 통해 현재 index에서 A가 연속되는 구간이 어디까지인지 파악을 한다. 이렇게 구해진 next는 연속된 A 구간의 마지막 A의 인덱스를 가리킨다.

 

위에서 설명한 ①, ②, ③의 값은 각각 다음과 같다.

① = i

② = i

③ = len(name) - next

 

 

코드 (deprecated!!)

def solution(name):
    answer = 0
    min_move = len(name) - 1
    next = 0
    
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        min_move = min(min_move, i + i + len(name) - next)
    answer += min_move
    return answer

 

---

(2022.01.10) 해당 글을 읽어주신 분들께서 제가 작성한 코드의 예외 케이스를 발견해주셨습니다. 지나치지 않고 피드백 주셔서 정말 감사합니다!!(알림이 따로 뜨지 않아서 댓글이 달린지도 몰랐습니다. 늦어서 죄송합니다ㅠㅠㅠ)

 

프로그래머스에서 제공하는 테스트 코드는 전부 통과하여서 몰랐었네요!

 

피드백 주신 테스트 케이스는 다음과 같습니다.

"ABABAABA"  -> 9가 나와야하는데 10이 나옴

"AAAABABAAAA" -> 8이 나와야하는데 9가 나옴

 

문제 해결을 해보려고 고민을 해본 결과, 해당 케이스들의 공통점은 마지막이 "A"로 끝난다는 것이었습니다.

마지막이 "A"로 끝나는 경우에는 (len(name) - 1)만큼 이동할 필요가 없습니다.

마지막이 n개의 "A"로 끝나는 경우, (len(name) - n - 1)만큼만 이동하면 됩니다. 

 

기존 코드에서 이동 거리의 최소값을 담는 min_move라는 변수의 초기값은 len(name) - 1인데 이를 name의 뒤에 붙은 "A"의 갯수만큼 더 빼주는 로직을 추가하여 해당 케이스를 통과시킬 수 있었습니다.

 

코드

def solution(name):
    answer = 0
    min_move = len(name) - 1
    next = 0
    
    while name[min_move] == 'A' and min_move > 0:
        min_move -= 1
    
    if (min_move < 0):
        return answer
        
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        min_move = min(min_move, i + (i + len(name)) - next)
    answer += min_move
    return answer