코드
def greedy_search(distance, cur_pos, moves, change_count):
if moves >= len(distance): return
change_at_current = distance[cur_pos]
distance[cur_pos] = 0
if sum(distance) == 0:
answer.append(moves + change_count + change_at_current)
greedy_search(distance.copy(), cur_pos + 1, moves + 1, change_count + change_at_current)
greedy_search(distance.copy(), cur_pos - 1, moves + 1, change_count + change_at_current)
def solution(name):
global answer
answer = []
distance = [min(ord(char) - ord('A'), 26 - (ord(char) - ord('A'))) for char in name]
greedy_search(distance, 0, 0, 0)
return min(answer)
풀이
우선 각 알파벳을 A 를 기준으로 양옆으로 인덱싱 해줘야합니다.
order = [ord(x)-ord('A') if ord(x) <= 78 else 26-(ord(x)-ord('A')) for x in name] 이 코드가 그 역할을 하는 것인데 저는 아스키 코드를 이용했지만 그냥 알파벳 수기로 써놓고 인덱싱 하는게 편합니다.
greedy
greedy 함수는 조이스틱을 양옆으로 움직이며 조작횟수를 카운팅 해주는 함수입니다. 조이스틱을 단방향으로만 움직여 계산을 하면
이런 반례가 나왔을 때 절대 답을 못찾습니다.
greedy(order, cur, move, change)
order: 알파벳과A와의 거리 를 모아둔 리스트입니다. 조작을 끝내면 0으로 바꿔줍니다.
cur: 현재 조이스틱이 머물고 있는 커서의 인덱스 입니다.
move: 조이스틱을 양옆으로 움직인 횟수
change: 조이스틱을 위아래로 움직인 횟수
move 횟수가 name 횟수를 넘어가면 그 branch는 없애는 식으로 재귀를 짰습니다.
def greedy(order, cur, move, change) :
if move >= len(order) : return
change_ = order[cur]
order[cur] = 0
if sum(order) == 0 :
answer.append(move+change+change_)
return
greedy(order.copy(), cur+1, move+1, change+change_)
greedy(order.copy(), cur-1, move+1, change+change_)
def solution(name = 'JEROEN'):
global answer
answer = []
order = [ord(x)-ord('A') if ord(x) <= 78 else 26-(ord(x)-ord('A')) for x in name]
greedy(order, 0, 0, 0)
return min(answer)