조이스틱
풀이과정
- 좌우이동
방법1.
조작 횟수가 최소가 되는 경우는 세 가지가 있다.
①오른쪽으로만 이동: 알파벳 이름을 완성할 때까지 오른쪽으로만 이동한다.
②왼쪽으로만 이동: 알파벳 이름을 완성할 때까지 왼쪽으로만 이동한다.
③오른쪽으로 이동하다가 왼쪽으로 방향 전환: 최소로 이동하려면 방향 전환 횟수가 최대 1회여야 한다. 문제 조건에서 ◀방향일 때만 첫번째 알파벳에서 마지막 알파벳으로 커서 이동이 된다고 써있으므로 왼쪽→오른쪽 방향 전환은 고려하지 않고 오른쪽→왼쪽 방향 전환만 고려하도록 한다.
방법2.
조작이 필요한 알파벳 중 현재 위치와 가장 가까운 알파벳으로 이동해가며 이름을 완성한다. 마찬가지로 ◀방향일 때만 첫번째 알파벳에서 마지막 알파벳으로 이동한다. - 상하이동
'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 중 기본값인 'A'를 제외한 25자의 가운데인 'N'을 기준으로 'N'보다 앞쪽 알파벳이면 조이스틱을 ▲방향으로 움직여 알파벳을 완성하고 'N'보다 뒷쪽 알파벳이면 ▼방향으로 움직여 알파벳을 완성한다.
- name 리스트를 for문을 돌려 'A'가 아닌 알파벳들(조작이 필요한 경우)을 change 리스트에, 해당 알파벳들의 인덱스들(0 제외)을 index 리스트에 저장한다.
- 좌우이동
방법1.
①오른쪽으로만 이동, ②왼쪽으로만 이동, ③오른쪽으로 이동하다가 왼쪽으로 방향 전환의 세 가지 경우 중 조작 횟수가 최소인 경우를 구해 answer에 더한다.
①오른쪽으로만 이동할 경우 조작 횟수: index 리스트의 최댓값 (조작해야하는 알파벳 중 마지막 알파벳의 인덱스)
②왼쪽으로만 이동할 경우 조작 횟수: name 리스트의 길이 - index 리스트의 최솟값 (조작해야하는 알파벳 중 첫번째 알파벳의 인덱스)
③오른쪽으로 이동하다가 왼쪽으로 방향 전환할 경우 조작 횟수: index 리스트를 for문을 돌려 현재 위치에서 방향 전환할 때의 이동 횟수를 모두 구한 것들의 최솟값
방법2.
현재 위치에서 앞뒤의 조작이 필요한 알파벳들 중 더 가까운 쪽으로 이동해간다.
현재 위치가 0인 경우(초기상태), 조작이 필요한 알파벳 중 첫번째인 경우(마지막 알파벳으로 이동 가능), 조작이 필요한 알파벳 중 마지막인 경우(첫번째로 이동 불가, 왼쪽으로만 이동 가능)로 나눠 앞뒤 알파벳과의 거리를 비교한 후 더 가까운 쪽으로 이동한다. 알파벳을 수정해가며 이동하므로 다른 경우는 존재하지 않는다. 알파벳 이름이 완성될 때까지 반복한다. - 상하이동
change 리스트를 for문을 돌려 현재 알파벳이 'N'보다 앞쪽이면 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'에서의 인덱스를 구해 answer에 더한다. 현재 알파벳이 'N'보다 뒷쪽이면 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'을 뒤집은 문자열에서의 인덱스+1을 answer에 더한다.
Python Code
방법1.
def solution(name):
answer = 0
namelist = list(name) #문자열을 list로 변환
N = len(namelist)
change = [] #조작이 필요한 알파벳들 저장
index = [] #조작이 필요한 알파벳들의 인덱스 저장(0제외)
for i, v in enumerate(namelist):
if v != 'A': #'A'가 아니면 조작이 필요함
change.append(v)
if i != 0: #시작 위치가 0이므로 0일 때는 좌우이동이 필요없기 때문에 제외
#(ex. 'BAAAA'일 경우 좌우이동 필요없음)
index.append(i)
right = max(index) #오른쪽으로만 이동하는 경우
left = N-min(index) #왼쪽으로만 이동하는 경우
rightleft = max(right, left) #오른쪽으로 이동하다가 왼쪽으로 방향 전환할 경우, 최솟값을 구해야하므로 최댓값으로 초기화함
#rightleft를 구하기 위한 for문
for i in range(len(index)-1): #조작이 필요한 마지막 알파벳에서 방향 전환하는 경우는 없으므로 index 리스트의 마지막 원소는 제외함
#(ex. 'ABBAAC'의 경우 'C'에서 방향전환하는 경우는 없음)
temp = 2*index[i] + (N-index[i+1]) #index[i]번째 알파벳에서 방향 전환할 경우의 이동 횟수
rightleft = (temp if temp<rightleft else rightleft) #이동 횟수의 최솟값 저장
answer += min(right, left, rightleft) #좌우이동의 세 가지 경우 중 최솟값을 더함
alphabet = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
for i, v in enumerate(change):
if v > 'N':
temp = list(reversed(alphabet)) #'N'보다 뒷쪽 알파벳일 때는 역순으로
print(temp.index(v) + 1)
answer += temp.index(v) + 1
else:
print(alphabet.index(v))
answer += alphabet.index(v)
return answer방법2.
def solution(name):
answer = 0
namelist = list(name)
N = len(namelist)
change = []
index = []
for i, v in enumerate(namelist):
if v != 'A':
change.append(v)
if i != 0:
index.append(i)
loc = 0 #현재 위치
while index: #index에 원소가 존재하는 동안
if loc == 0: #초기 상태
if index[0] <= N-index[-1]: #조작이 필요한 첫번째 알파벳과 마지막 알파벳 중 첫번째와 더 가까운 경우
answer += index[0]
loc = index[0]
else: #마지막 알파벳과 더 가까운 경우
answer += N-index[-1]
loc = index[-1]
elif loc == index[0]: #현재 위치가 조작이 필요한 첫번째 알파벳
if len(index) > 1: #조작이 필요한 알파벳이 2개 이상
if index[1]-index[0] <= index[0] + N-index[-1]: #알파벳이 3개 이상:
#다음 알파벳과 마지막 알파벳 중 다음 알파벳과 더 가까운 경우
#알파벳이 2개: 오른쪽으로 이동하는 게 왼쪽으로 이동하는 것보다 가까운 경우
answer += (index[1] - index[0])
loc = index[1]
del index[0] #수정이 완료된 위치는 삭제
else: #마지막 알파벳과 더 가까운 경우, 왼쪽으로 이동하는 게 더 가까운 경우
answer += (index[0] + N-index[-1])
loc = index[-1]
del index[0]
else: #조작이 필요한 알파벳이 1개
del index[0] #수정 완료 후 while문 끝
elif loc == index[-1]: #현재 위치가 조작이 필요한 마지막 알파벳
if len(index) > 1:
answer += (index[-1] - index[len(index)-2]) #왼쪽으로만 이동
loc = index[len(index)-2]
del index[-1]
alphabet = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
for i, v in enumerate(change):
if v > 'N':
temp = list(reversed(alphabet))
print(temp.index(v) + 1)
answer += temp.index(v) + 1
else:
print(alphabet.index(v))
answer += alphabet.index(v)
return answer오류와 해결
처음에 오른쪽으로만 이동하는 경우와 왼쪽으로만 이동하는 경우만 처리했더니 테스트케이스 11번이 통과되지 않았다. 질문을 보다가 오른쪽으로 이동하다가 왼쪽으로 이동하는 경우도 있다는 걸 알게 돼서 그 부분을 처리하느라 시간이 오래 걸렸다. 여러 방법으로 시도해봤는데 어떤 코드는 테스트케이스 11번은 통과됐지만 4번과 7번이 통과되지 않았다.(이유는 지금도 모르겠음...) 위에 정리한 방법1로 했더니 모든 테스트케이스가 통과됐다. 다만 방법1은 그리디가 아니라 완전탐색에 가까운 듯하다. 그래서 그리디로 풀어보려고 방법2로 했더니 모든 테스트케이스가 통과되긴 했지만 예외가 몇 개 발견되었다. "BABAAAAB"의 경우 좌우이동의 최소 횟수는 5이지만 방법2의 코드로 돌리면 6으로 처리된다. 아무래도 테스트케이스가 꼼꼼하지 않은 것 같다.
(●⁰౪⁰●)