https://school.programmers.co.kr/learn/courses/30/lessons/42860
def find_string(name, start):
cnt = 0
for idx in range(start, len(name)):
if name[idx] == 'A':
cnt += 1
else: break
return cnt
def solution(name):
answer = 0
# 상하로 조이스틱 이동하는 최솟값 (고정)
for spell in name:
answer += min(ord(spell) - ord('A'), ord('Z') - ord(spell) + 1)
# 좌우로 조이스틱 이동하는 최솟값
# 1. 가장 긴 AA..A 찾기
longest_a = [0 , 0] # [문자열 시작 인덱스, 문자열 길이]
for idx in range(len(name)):
if name[idx] == 'A':
if find_string(name, idx) > longest_a[1]:
longest_a[0] = idx
longest_a[1] = find_string(name, idx)
# 2. 가장 긴 AA..A 문자열까지 도달하는데 좌우 중 어느 방향이 최솟값인지 판별
if longest_a[1] == 0:
# name 에 A가 하나도 포함되어 있지 않음
# -> 그냥 차례대로 움직임
return answer + len(name) - 1
if longest_a[0] == 0:
# 거꾸로 이동, 되돌아올 필요 없음
return answer + len(name) - longest_a[1]
if longest_a[0] + longest_a[1] == len(name):
# 그대로 이동, 되돌아갈 필요 없음
return answer + longest_a[0] - 1
# A..A 문자열이 중간에 있음 (되돌아갈/올 수 있음)
# 그대로 이동하고 되돌지 않는 경우
ans1 = 0
for idx in range(len(name) - 1, -1, -1):
if name[idx] != 'A':
ans1 = idx
break
# 거꾸로 이동하고 되돌지 않는 경우
ans2 = 0
for idx in range(len(name)):
if name[idx] != 'A':
ans2 = len(name) - idx
break
x = longest_a[0]
y = len(name) - longest_a[0] - longest_a[1]
return min(2 * (x-1) + 1 + (y-1), 1 + 2 * (y-1) + 1 + (x-1), ans1, ans2) + answer
이 문제는 A로만 이루어진 가장 긴 문자열(AA..A)
을 기준으로 이동하는 횟수를 생각하면 된다.
A로만 이루어진 가장 긴 문자열이 맨 앞에 있을 경우
: 거꾸로 (뒤에서부터) 이동한다
A로만 이루어진 가장 긴 문자열이 맨 뒤에 있을 경우
: 그대로 (앞에서부터) 이동한다
A로만 이루어진 가장 긴 문자열이 중간에 있을 경우
: 거꾸로 이동하는 경우, 그대로 이동하는 경우, 거꾸로 가다가 되돌아오는 경우, 그대로 가다가 되돌아오는 경우 - 이 네가지 중 최소 이동 거리를 찾으면 된다
나는 처음엔 되돌아오는 경우도 있다는 걸 간과해서 막혔고, 그 다음엔 3번 경우에서도 되돌아오지 않을 때 최소일 경우가 있다는 걸 간과해서 막혔었다.