조이스틱 [자바]

 

🧫 문제 분석

✔️ 출처

조이스틱 level 2

📖 문제

 

탐욕법인데 

정말 어려웠다. 

 

 

먼저 알파벳 변경은 매우 쉽다. 

주어진 알파벳 - 'A' (앞으로 가는 경우) 와  'Z'  - 주어진 알파벳 + 1 (뒤로 가는 경우)

최솟값을 answer에 다 더해주면 된다. 

 

 

문제는 커서 이다.

 

시계 방향, 반시계 방향으로 인덱스 돌리는게 도무지 떠오르지 않아서 삽질을 엄청했다.

 

배열에서 두 인덱스 사이의 거리 최솟값

시계방향, 반시계 방향의 최솟값을 찾으면 된다.

// a b 인덱스 ,n은 배열의 크기
//       반시계방향         시계방향
Math.min((a - b + n) % n, (b - a + n) % n));

 

 

어떻게 해서든 풀어보자는 마인드로 

문자 길이가 20인걸로 보아 

백트래킹 써도 되겠다 싶어서 백트래킹으로 최솟값을 구했다. 

 

 

내가 만든 테스트 케이스 (반례)를 남기겠다.

 

"ABBBAAB" 9
"ABAAAYYA" 10

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {

    // 그래프 (A를 제외한 그래프 생성) [인덱스 정보를 가짐]
    // 현재 알파벳 위치에서 다음 알파벳 가는데 비용 계산

    class Alpha {
        int next, cost;

        public Alpha(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

    int min = 1000000;

    ArrayList<Alpha>[] graph;
    boolean[] visited;

    public int solution(String name) {
        int len = name.length();
        graph = new ArrayList[len];
        visited = new boolean[len];

        int sum = 0; // 한 위치의 알파벳 최소 비용 합
        for (int i = 0; i < len; i++) {
            // A부터 가는 방법, A뒤로 Z부터 가는 법 중 최소 비용
            sum += Math.min(name.charAt(i) - 'A'
                    , ('Z' - name.charAt(i)) + 1);

            // 리스트 생성
            graph[i] = new ArrayList<>();
        }


        // 거리 값 저장
        // 다음거 - 현재 인덱스 vs 글자 최대 길이 + 현재 알파벳인덱스 - 다음 알파벳 인덱스     
        for (int i = 0; i < len; i++) {
            if (i != 0 && name.charAt(i) == 'A') continue;

            for (int j = 0; j < len; j++) {
                if (name.charAt(j) != 'A' && i != j) {
                    
                    // 두 위치 사이 반시계, 시계방향 거리 구하기
                    // Math.min((a - b + n) % n , (b - a + n) % n)
                    int minCost = Math.min((j - i + len) % len, (i - j + len) % len); // 왼쪽 이동 , 오른쪽 이동 최솟값
                    graph[i].add(new Alpha(j, minCost));
                }
            }
        }

        visited[0] = true;
        dfs(0, 0, 0);
        
        return sum + min;
    }


    private void dfs(int idx, int cost, int depth) {

        if (depth == graph[0].size()) {
            min = Math.min(min, cost);
            return;
        }

        for (int i = 0; i < graph[idx].size(); i++) {
            Alpha alpha = graph[idx].get(i);

            if (!visited[alpha.next]) {
                visited[alpha.next] = true;
                dfs(alpha.next, cost + alpha.cost, depth + 1);
                visited[alpha.next] = false;
            }
        }
    }


}

 

🔅 다른 사람 풀이 이해해보기

프로그래머스 다른 사람 풀이를 보면 제일 먼저 보이는 풀이가 있는데 매우 인상적이였다. 

for(int i=0;i<length;i++){
            int next=i+1;
            while(next<length && name.charAt(next)=='A'){
                next++;
            }                
            min=Math.min(min,i+length-next+Math.min(i,length-next));
        }

나도 이해해보고 익혀보자

 

핵심 

인덱스 0(시작점)을 거쳐서 좌 우로 이동하는데 

A가 연속되는 부분을 제외한 위치를 앞 뒤로 가져가고 ex) BBBAAABBB 면  BBBAAABBB 색칠한 앞 뒤 위치를 가짐

이때 비용을 더해준다. 

 

이 부분이  i + length - next  이다.

 

 

0을 기준으로 앞으로 갔다가 뒤로 갈건지

뒤로 갔다가 앞으로 갈 건지에 대한 비용을 더해주면 된다 .

 

 

그림으로 이해해보면 

A를 제외한 앞뒤 인덱스 이동 비용

 

0 ->(앞으로) 2 -> 0 ->(뒤로) 6

0 ->(뒤로) 6 -> 0 -> 2(앞으로)

 

이 둘 중 최솟값을 더해주면 된다.

이부분이 Math.min(i, length - next) 이다. 

 

 

 

 

 

❗ 오답노트 / 필요한 지식

1. 정말 많은 걸 배운 시간이였다. 시계 반시계 원형 배열 계산법, 앞 뒤 이동이 가능할 때 최소 이동 값 구하는 방법 등.. 
2. 잘 기억하자.