[프로그래머스] 조이스틱

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

문제 분석

[제한 사항]

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

 

위와 같이 조이스틱을 조작하며 주어진 name을 만들기 위해 최소한의 조작 횟수를 구하는 문제이다.

초기 문자 상태는 모두 A 이다.

문제 접근

우선 해당 문자를 만들기 위한 조작 횟수를 계산하여 해당 문자에 도달하기 위해 필요한 조작 횟수를 담은 배열을 만들어 주었다.

JAZ -> [9, 0, 1]

 

이것 저것 시도해 보면서 name 의 길이가 충분이 작기 때문에 완전탐색을 시도하였다.

dfs 를 이용한 완전탐색을 이용해 문제를 해결하였다.

 

코드

import java.util.*;

class Solution {
    static int answer = Integer.MAX_VALUE;
    
    public int solution(String name) {
        char[] nameArr = name.toCharArray();
        int[] distanceArr = new int[nameArr.length];

        for(int i=0; i<distanceArr.length; i++){
            distanceArr[i] = nameArr[i] - 'A' < 26 - (nameArr[i] - 'A') ? nameArr[i] - 'A' : 26 - (nameArr[i] - 'A');
        }
        dfs(Arrays.stream(distanceArr).sum(), 0, 0, distanceArr, 0);
        System.out.println(Arrays.toString(distanceArr));

        return answer;
    }
    
    public static void dfs(int sum, int cost, int cur, int[] distanceArr, int depth){
        if(sum == 0){
            answer = Math.min(answer, cost);
            return;
        }

        if (depth == distanceArr.length) {
            return;
        }

        if (depth == 0) {
            cost += distanceArr[cur];
            sum -= distanceArr[cur];
            distanceArr[cur] = 0;
        }

        int front = cur + 1 < distanceArr.length ? cur +1 : 0;
        int back = cur - 1 >= 0 ? cur - 1 : distanceArr.length - 1;

        // 앞으로 이동
        int frontCost = distanceArr[front];
        distanceArr[front] = 0;
        dfs(sum - frontCost, cost + 1 + frontCost, front, distanceArr, depth+1);
        distanceArr[front] = frontCost;

        // 뒤로 이동
        int backCost = distanceArr[back];
        distanceArr[back] = 0;
        dfs(sum - backCost, cost + 1 + backCost, back, distanceArr, depth+1);
        distanceArr[back] = backCost;
    }
}