난이도 : 레벨 2
유형 : 그리디
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42860
문제 요약
이름을 A로 가득한 상태에서 시작해서, 목표 문자열 name을 만든다.
커서는 처음에 0번 인덱스에 있다.
두 가지 비용을 합산한 최소값을 구해야 한다:
1. 각 자리 문자를 A에서 목표 문자로 바꾸는 상·하 이동(위/아래)
2. 커서를 좌·우로 움직이는 이동
1. 상하이동
알파벳은 총 26글자 (A ~ Z).
- 위로 이동하는 경우: 'A' → 'B' → 'C' → ... (앞으로 가기)
- 아래로 이동하는 경우: 'A' → 'Z' → 'Y' → ... (뒤로 가기)
즉, 어떤 문자 ch에 도달하려면:
앞으로만 갔을 때: ord(ch) - ord('A')
뒤로 갔을 때: 26 - (ord(ch) - ord('A'))
둘 중 더 작은 값을 선택하면 된다.
ord() 는 파이썬에서 문자를 유니코드 정수값으로 바꿔주는 함수이다.
ord('A') 는 65이고
ord('B') 66 이다.
ord('B') - ord('A') 를 해주면 몇번 방향키를 눌러야하는 지 알 수 있다.뒤로 갔을 때 식은 Z - A 는 25인데 정방향으로 가면 25이지만 역방향으로 한번 톡 누르면 1이기 때문에
26 - ord의 차잇값 을 해주면 뒤로 갔을때의 값이 나올 수 있다.
2. 좌우이동
커서는 문자열의 인덱스(0~n-1)를 좌우로 움직일 수 있다.
단순히 오른쪽으로만 쭉 가면 n-1번 이동. (n-1번 오른쪽 키 딸깍 하면 맨 오른쪽 도착)
하지만 중간에 'A'가 연속으로 나오면, 왼쪽으로 가는게 더 빠를 수 있다.
ex) ZAZ 의 경우 오른쪽으로 가려면 0번 인덱스에서 2번 인덱스까지 두번 눌러야하지만, 왼쪽은 한번만 누르면 된다.
즉 좌우이동은
- 그냥 오른쪽으로만 쭉 가는 게 더 빠른 경우
ex) ABCDEF
- 이동 횟수 = n - 1
- 앞으로 갔다가 뒤로 오는게 더 빠른 경우
ex) ZZAAAAAAAAAABC
- 이동 횟수 = 2*i + (n - next_idx)
- 뒤로 갔다가 앞으로 오는 게 더 빠른 경우
ex) ZZZAAAAAZ
- 이동 횟수 = i + 2*(n - next_idx)
이 세 경우를 구하고 최소 값을 구해주면 된다.
여기서 next_idx 는 i 다음부터 시작해서 연속된 'A' 구간이 끝나고 처음으로 'A'가 아닌 문자가 나오는 위치
전체 코드 및 풀이
def solution(name):
n = len(name)
# 1.상하 이동(문자 바꾸기) 비용 구하기 (A에서 특정 문자까지 위/아래로 몇 번 이동해야 하는가)
def updown_cost(ch):
diff = ord(ch) - ord('A')
return min(diff, 26 - diff) # 위로 가는 경우, 아래로 가는 경우 중 작은 값
change = 0
for ch in name:
change += updown_cost(ch)
# 2. 좌우 이동 비용 구하기
move = n - 1 # 오른쪽으로 이동
for i in range(n):
next_idx = i + 1
# i 뒤로 연속된 'A' 구간 찾기
while next_idx < n and name[next_idx] == 'A': # n의 범위 내에서 다음 인덱스 값이 A라면
next_idx += 1
move = min( move,
2*i + (n - next_idx),
2*(n - next_idx) + i )
return change + move