[알고리즘][3] 조이스틱
2023. 9. 8. 12:38ㆍ알고리즘 풀이
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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
출처
※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2022년 1월 14일 지문 수정 및 테스트케이스가 추가되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.
나의 풀이
- 풀기는 풀었지만 다시는 풀고 싶지 않은 문제
- 어떻게 풀어야할지 아이디어를 내야 하는 난관 1
- A 연속된 위치를 저장해야 하는 난관 2
- 그 위치를 이용해서 경우의 수를 나누어서 최소가 나오도록 하는 계산식을 써야 하는 난관 3
- 어려운 난관들이 연속해 있는 매우 어려운 문제이다.
- 실전에서는 맨 나중으로 미루고 시간이 많이 남으면 풀겠다.
- 왜냐하면 방법을 알아도 구현하기가 어렵기 때문이다.
def solution(name):
# 최소이므로 그리디, DP, 탐색
# 완전 탐색하기에는 경우의 수가 많아짐
# 중간 결과를 이용할 수도 없음
# 따라서 그리디
up_down = 0
for char in name:
up_down += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
if name == 'A' * len(name):
return 0
# left_right의 최댓값
left_right = len(name) - 1
candidates = []
max_length = -float('inf')
for idx, start_char in enumerate(name):
if start_char != "A":
continue
first_idx = idx
cur_idx = idx
length = 0
while length <= len(name):
cur_char = name[cur_idx]
if cur_char != "A":
end_idx = cur_idx - 1
break
length += 1
cur_idx = (cur_idx + 1) % len(name)
if max_length < length:
max_length = length
candidates = []
candidates.append((first_idx, end_idx, length))
elif max_length == length:
candidates.append((first_idx, end_idx, length))
for candidate in candidates:
first_idx, end_idx, length = candidate
if end_idx == -1 or end_idx >= first_idx:
left_right = min(left_right, 2 * (max(0, first_idx - 1)) + len(name) - end_idx - 1, 2 * (len(name) - end_idx - 1) + max(0, first_idx - 1))
else:
left_right = min(left_right, first_idx - 1, len(name) - end_idx - 1)
return up_down + left_right
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘][3][RE] 사칙연산 (1) | 2023.09.11 |
---|---|
[알고리즘][3] N으로 표현 (0) | 2023.09.10 |
[알고리즘][3][X] 전력망을 둘로 나누기 (0) | 2023.09.07 |
[알고리즘][3] 소수 찾기 (0) | 2023.09.06 |
[알고리즘][3] 디스크 컨트롤러 (0) | 2023.09.05 |