[프로그래머스 알고리즘 고득점 kit] 탐욕법(Greedy) 조이스틱 - JAVA

 

🧐 문제

문제 :
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

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

 

---

✅ 접근 방식

index:    0  1  2  3  4  5  6
name:    J  B  Z  Z  A  A  Z

위의 예제를 통해 설명하고자 한다.

 

이 문제의 핵심은 최소 이동 거리를 찾는 것이 핵심이다.

문제의 접근 방식은 다음과 같이 크게 두 가지로 분류할 수 있다.

---

1️⃣ 알파벳 찾는 최솟값 (▲, ▼)

현재 위치에서 답에 해당하는 알파벳으로 가는 경우의 수는 총 두 가지이다.

• ▲으로 이동
• ▼으로 이동

두 개의 경우의 수를 구하는 로직을 작성한다면 해당 최솟값은 쉽게 구할 수 있다.

index가 0에 해당할 때, J를 찾기 위해서는 A에서~J까지의 횟수 또는 A->Z로 이동한 후 Z~J까지의 횟수를 구하면 된다.

updown = Math.min(name.charAt(index) - 'A', 'Z' - name.charAt(index) + 1)

따라서 위와 같이 쉽게 알파벳을 찾는 최솟값을 구할 수 있다.

---

2️⃣ 최소 이동 거리를 찾는 최솟값 (◀, ▶)

최소 이동거리를 찾는 최솟값을 찾는 과정에서 greedy 탐색이 사용된다.

경우의 수는 크게 다음과 같이 세 가지로 생각할 수 있다.

---

☑️ 1. 그냥 오른쪽으로 쭉

가장 기본적으로 생각할 수 있는 경우의 수이다.

 

J를 시작으로 오른쪽으로 쭉 가면서 알파벳을 차례로 바꿔주는 경우의 수이다.

그렇다면 이동해야 하는 거리는 name.length - 1(= 6)가 된다.

 

그런데, 여기에서 고려해 볼 수 있는 점은 과연 A가 있는 곳도 우리가 지나쳐야 하는가이다.

왜냐하면 초기값이 A로 설정되어 있기 때문에 A가 중복되어 나오는 곳은 오히려 그냥 쭉 가는 것보다 돌아서 가는 것이 더 짧은 거리일 수 있기 때문이다.

---

☑️ 2. 오른쪽으로 갔다가 돌아서 왼쪽으로 가기

A가 나오는 부분은 바꾸지 않아도 된다.

따라서 오른쪽으로 가다가 A가 나오는 순간 왼쪽으로 돌아서 가는 경우의 수를 구할 수 있다.

이렇게 가는 방식이 그냥 쭉 가는 방식보다 최소거리일 수 있기 때문이다.

 

이때 구해야 할 index는 다음과 같다.

1.  x : 원점으로부터 오른쪽으로 이동해 첫 번째로 A가 나오는 전까지의 index  = 3
2.  y : x부터 시작해서 A가 아닌 문자가 나오는 index = 6

 

그렇다면 이동거리는 다음과 같이 구할 수 있다.

오른쪽 x만큼 이동
+
왼쪽으로 x만큼 이동
+
원점에서 뒤로 (length - y)만큼 이동

이렇게 구한다면 총 이동거리는 3 + 3 + (7-6) = 7이다.

---

☑️ 3. 왼쪽으로 돌아서 갔다가 오른쪽으로 쭉

위에서 다루었던 방식은 먼저 오른쪽으로 간 다음에 뒤로 돌아서 가는 방식이었다.

 

그렇다면 반대의 경우의 수도 고려해봐야 한다.

반대의 경우의 수는 왼쪽으로 돌아간 다음 다시 오른쪽으로 쭉 가는 경우의 수이다.

 

이때도 마찬가지로 index 두 개를 설정한다.

1.  x : 원점으로부터 오른쪽으로 이동해 첫 번째로 A가 나오는 전까지의 index  = 3
2.  y : x부터 시작해서 A가 아닌 문자가 나오는 index = 6

그렇다면 이동거리는 다음과 같이 구할 수 있다.

뒤로 (length-y)만큼 이동
+
뒤에서부터 다시 원점으로 이동(=length-y)
+
원점에서 앞으로 x까지 이동

이렇게 구한다면 총 이동거리는 1 + 1 + 3 = 5이다.

즉, 이렇게 이동하는 방식이 최소 이동거리이다.

---

🚩 NOTE

즉, 우리가 구해야 하는 것은 최적의 X의 인덱스이다.

그러나 순회 없이 최적의 x의 인덱스를 구하는 것은 쉽지 않다.

("JAZZAZ"와 같이 A 두 개 사이에 A가 아닌 알파벳이 껴있는 경우가 있기 때문에 결국 탐색을 시도해야 한다.)

 

따라서, name의 인덱스를 순회하며 매번 x와 y의 인덱스를 업데이트해 주고, 그에 따른 최소 거리를 업데이트할 것이다.(Greedy 탐색) 위의 예제에 따르면 for문의 index가 x의 index인 4가 되었을 때 최소거리가 5로 업데이트될 것이고 이를 출력할 수 있게 된다.

---

✅ 코드 답안 - JAVA

class Solution {
    public int solution(String name) {
        int answer = 0;
        int length = name.length();
        int move = length - 1;
        int y;
        
        for (int x = 0; x < length; x++){
            answer += Math.min(name.charAt(x) - 'A', 'Z' - name.charAt(x) + 1);
            
            y = x + 1;
            while (y < length && name.charAt(y) == 'A'){
                y ++; // A가 더이상 나오지 않는 index
            }
            
            move = Math.min(move, (Math.min(x+x+(length-y), x+(length-y)+(length-y)))); 
        }
        
        
        return answer + move;
    }
}