programmers / 조이스틱 / python

코딩테스트 연습 - 조이스틱

자세한 해설

한쪽으로만 가면서 계산하는 경우 외에도 오른쪽으로 가다 왼쪽, 혹은 왼쪽으로 가다 오른쪽으로 가야 최적의 해가 나오는 경우가 있습니다.

따라서 모든 경우의 수를 만들어서 가장 낮은 횟수를 구하는 방향으로 풀었습니다.

 

• 우선 리스트 슬라이싱을 활용하여 한쪽으로 `i`만큼 밀린 name 2개를 만들어줍니다.
• name의 중간길이 미만으로 도는 이유는 그 이상으로 돌면 중복이 발생하기 때문입니다.

for i in range(len(name) // 2):
    left_moved = name[-i:]+name[:-i] 
    right_moved = name[i:]+name[:i]

• 오른쪽으로 가면서 답을 구하기 때문에 밀린 반대 방향으로 가기 위해서 오른쪽으로 밀린 name은 첫 문자를 제외하고 뒤집어줍니다. 왼쪽으로 밀린 name은 그대로 사용합니다.

    for n in [left_moved, right_moved[0]+right_moved[:0:-1]]:

• 이동한 횟수는 한쪽으로 간 횟수i + name의 길이만큼 간 횟수len(n) - 1 입니다.
  문자를 바꾼 횟수는 ord() 함수를 활용하여 ASCII 값으로 문자마다의 최적의 해를 구합니다.

        row_move = i + len(n)-1
        col_move = 0
        for c in map(ord, n):
            col_move += min(c - 65, 91 - c)

 

i 는 0부터 시작하기 때문에 방향을 틀지 않고 왼쪽 혹은 오른쪽으로만 가는 name도 자동으로 포함됩니다.

 

---

전체코드

def solution(name):
    if set(name) == {'A'}:
        return 0

    answer = float('inf')
    for i in range(len(name) // 2):
        left_moved = name[-i:]+name[:-i]
        right_moved = name[i:]+name[:i]
        for n in [left_moved, right_moved[0]+right_moved[:0:-1]]:
            while n and n[-1] == 'A':
                n = n[:-1]

            row_move = i + len(n)-1
            col_move = 0
            for c in map(ord, n):
                col_move += min(c - 65, 91 - c)

            answer = min(answer, row_move + col_move)

    return answer

잡담

매번 최적의 해를 구하기위해 어디로 갈지 정하면 코드가 너무 복잡해지고 예외를 처리하기가 힘들어서 시간이 오래걸렸습니다.

방향을 2번 바꾸는 경우는 답으로 될 수 없기 때문에 단순하게 방향을 0번 혹은 1번 바꾸는 모든 경우의 수를 만들어서 푸는게 차라리 낫겠다고 생각했고 구현이 훨씬 간단해졌습니다.

 

---

GitHub - bassyu/PS: ☑️ Problem Solving