조이스틱
문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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 |
해결 과정
조이스틱 문제는 프로그래머스의 코딩테스트 고득점 Kit 탐욕법( Greedy )에 속해있는 문제지만 22년 1월 테스트케이스가 추가되면서 완전탐색( Brute Force ) 문제에 가까워졌습니다.
[알고리즘] 완전 탐색, 브루트 포스 정의 | 종류 | 장단점 | 예시 (feat. Node.js Brute-Force-Search)
들어가며 알고리즘은 어떤 문제를 해결하기 위한 동작들의 절차입니다. 공간 복잡도와 시간복잡도를 고려해서 무조건 가장 빠르고 효율적인 알고리즘을 사용하면 되지 않을까라는 생각을 할
aiday.tistory.com
1. 알파벳을 변경한 횟수와 커서 이동 횟수를 저장하기 위한 변수를 선언해 주었습니다.
2. 이름을 하나씩 확인하기 위해 for loop을 돌려줍니다. 이때 이름의 인덱스도 같이 확인하기 위해 enumerate 함수로 접근합니다.
3. 알파벳 변경 횟수는 'A에서 B 방향으로 이동'과 'A에서 Z 방향으로 이동'중에서 최솟값으로 처리하고 저장해 줍니다.
4. 가장 중요한 연속된 A를 찾는 부분입니다. 연속된 A의 길이에 따라 최소 이동 방향이 달라지기 때문에 next 변수에 연속된 A의 값을 저장해 줍니다. 예를 들어 TAATAAAAAT 인 경우 4번째 T를 처리하기 위해서 2, 3번째의 연속된 AA를 건너는 것이 5,6,7,8,9번째의 연속된 AAAAA를 건너는 것보다 효율적입니다.
5. 커서의 이동 횟수는 '기존에 저장된 있는 값', '연속된 A의 왼쪽 시작', '연속된 A의 오른쪽 시작' 중에서 최솟값이 가장 효율적인 이동 횟수입니다.
6. 조이스틱 조작 횟수는 알파벳 변경 횟수와 커서 이동 횟수를 더한 값입니다. 두 값을 더해서 반환해 줍니다.
제출 코드
def solution(name):
# 알파벳 변경 횟수( 상하 이동 )
spell_move = 0
# 커서 이동 횟수, 이름의 길이 - 1( 좌우 이동 )
cursor_move = len(name) - 1
for i, spell in enumerate(name):
# 알파벳 변경 횟수, 위아래 중 최소 이동 값 ( 상하 이동 )
spell_move += min(ord(spell) - ord('A'), ord('Z') - ord(spell) + 1)
# 해당 알파벳 다음부터 연속된 A 문자열 찾기
next = i + 1
while next < len(name) and name[next] == 'A':
next += 1
# 아래 3가지 경우 중 최소 이동 값으로 갱신
# 1. 이전 커서 이동 값 ( 초기값 - 이름의 길이 - 1 )
# 2. 연속된 A의 왼쪽 시작
# 3. 연속된 A의 오른쪽 시작
cursor_move = min([ cursor_move, 2 * i + len(name) - next, i + 2 * (len(name) - next) ])
# 조이스틱 조작 횟수 = 알파벳 변경 횟수( 상하 이동 ) + 커서 이동 횟수( 좌우 이동 )
return spell_move + cursor_move
또 다른 풀이
def solution(name):
answer = 0
n = len(name)
def alphabet_to_num(char):
num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
return num_char[ord(char) - ord('A')]
for ch in name:
answer += alphabet_to_num(ch)
move = n - 1
for idx in range(n):
next_idx = idx + 1
while (next_idx < n) and (name[next_idx] == 'A'):
next_idx += 1
distance = min(idx, n - next_idx)
move = min(move, idx + n - next_idx + distance)
answer += move
return answer
Reference
