[Programmers] Q42860 조이스틱

[Programmers] Q42860 조이스틱

Question

Language: Python

해당 문제는 각각의 문자열의 위치에서 알파벳 변환을 수행해주면서 목표한 문자열을 만들기 위한 최소 변환 횟수를 구하는 문제이다.

문제에서 주어진 문자열의 길이가 짧으므로 모든 경우를 다 고려해서 진행해주면된다.

각각의 위치값에서 왼쪽으로 이동하는 경우, 오른쪽으로 이동하는 경우가 존재하므로 이를 모두 고려해서 최소 변환 횟수를 구하면 된다.

Solution

from math import inf
min_count=inf

def char_distance(char):
    return min(abs(ord(char)-ord('A')),26-abs(ord(char)-ord('A')))

def parse(name,n,depth,index,count):
    global min_count
    
    #n번의 이동을 수행하였거나, "A..." 초기 문자열로 만들어졌는 경우 재귀를 멈춘다.
    if depth==n or name == ["A"]*n:
        min_count=min(min_count,count)
        return
    
    #왼쪽 이동  
    for i in range(1,n):
        prev_index=(index-i)%n
        distance=char_distance(name[prev_index])
        if distance==0:
            continue
        temp=name[:]
        temp[prev_index]="A"
        parse(temp,n,depth+1,prev_index,count+distance+i)
        break
    
    #오른쪽 이동
    for i in range(1,n):
        next_index=(index+i)%n
        distance=char_distance(name[next_index])
        if distance==0:
            continue
        temp=name[:]
        temp[next_index]="A"
        parse(temp,n,depth+1,next_index,count+distance+i)
        break


def solution(name):
    length=len(name)
    name=list(name)
    #첫번째 자리에 대한 변환 처리
    distance=char_distance(name[0])
    name[0]="A"

    parse(name,length,0,0,distance)
    return min_count