(Python, Java) 프로그래머스 - 조이스틱

13 Jan 2022 in Algorithm on Programmers, Level2

[문제 링크]

Python 풀이

import sys
sys.setrecursionlimit(19 ** 6)

answer = int(1e9)

def solution(name):
    n = len(name)
    move = [0] * n
    for idx in range(n):
        move[idx] = min(ord(name[idx]) - ord('A'), ord('Z') - ord(name[idx]) + 1)

    dfs(move, 0, 0, n)

    return answer


def dfs(move, pos, tot, n):
    global answer

    # 현재 위치 처리
    tot += move[pos]
    move[pos] = 0

    # 모두 처리 한 경우
    if sum(move) == 0:
        answer = min(tot, answer)
        return

    # 왼쪽으로 
    left = pos
    left_cnt = 0
    while move[left] == 0:
        left = (left - 1 + n) % n
        left_cnt += 1
    prev = move[left]
    dfs(move, left, tot + left_cnt, n)
    move[left] = prev  # 원상 복구

    #  오른쪽으로
    right = pos
    right_cnt = 0
    while move[right] == 0:
        right = (right + 1) % n
        right_cnt += 1
    prev = move[right]
    dfs(move, right, tot + right_cnt, n)
    move[right] = prev  # 원상 복구

Java 풀이

import java.util.Arrays;

class Solution {
    int answer = Integer.MAX_VALUE;

    public int solution(String name) {
        int n = name.length();
        int[] move = new int[n];

        // 초기화
        for (int idx = 0; idx < n; idx++) {
            move[idx] = Math.min('Z' - name.charAt(idx) + 1, name.charAt(idx) - 'A');
        }

        dfs(move, 0, 0, n);

        return answer;
    }

    private void dfs(int[] move, int pos, int tot, int n) {
        tot += move[pos];
        move[pos] = 0;

        if (Arrays.stream(move).sum() == 0) {
            answer = Math.min(answer, tot);
            return;
        }

        // 오른쪽 이동
        int move_cnt = 0;
        int next = pos;

        while (move[next] == 0) {
            move_cnt += 1;
            next = (next + 1) % n;
        }
        int prev = move[next];
        dfs(move, next, tot + move_cnt, n);
        move[next] = prev;

        // 왼쪽 이동
        move_cnt = 0;
        next = pos;

        while (move[next] == 0) {
            move_cnt += 1;
            next = (next - 1 + n) % n;
        }
        prev = move[next];
        dfs(move, next, tot + move_cnt, n);
        move[next] = prev;

    }
}