[프로그래머스 / Java] - 조이스틱

문제 설명

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

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

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

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.

따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

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

 

정답 설명

문제 파악

이번 문제에서의 조이스틱 이동은 크게 두가지로 구분할 수 있다. 바로 상, 하로의 알파벳 변경 움직임과 좌,우로의 커서 변경 움직임이다.

 

이 때, 상, 하로의 움직임 횟수를 먼저 고려해 보자.

예를 들어, 만들고자 하는 이름이 "JAZZ"인 경우, 우리는 총 몇 번의 상,하 움직임을 가져야 하는가?

이는 각 자리에서의 최소 움직임 횟수의 합으로 쉽게 구할 수 있다.

Z 알파벳의 경우 A부터 알파벳 순서대로 25번의 움직임을 취하는 것 보다, 역순으로 1번의 알파벳 움직임을 취하는 것이 최선의 선택이 되는 것이다.

 

그렇다면, 좌, 우로의 움직임의 횟수는 어떻게 될까? 즉, 어떤 순서로 각 자리의 알파벳을 변경시켜야 할까?

만들고자 하는 이름이 "UEFUAAAA" 인 경우에는 앞에서 부터 차례대로 변경 시켜 3 번의 오른쪽 움직임을 취하는 것이 최선의 선택이다. 반대로, "AAAFFF"의 경우에는 뒤에서부터 차례대로 변경 시켜 3 번의 왼쪽 움직임을 취하는 것이 최선의 선택이다. 그렇다면, "BCAAAAAAZK"의 경우에는 어떨까? 이 경우에는 "오른쪽, 왼쪽, 왼쪽, 왼쪽"의 4 번의 움직임을 취하는 것이 최선의 선택이다.

 

이번 문제의 핵심은, 어떤 순서로 각 자리의 알파벳을 변경시키는 것이 최적의 방법인지를 찾는 것 이다.

조금 더 단순화 시키면, 우리에게 필요한 것은 좌, 우 이동의 최소 횟수를 구하는 것이다.

 

이름만 보고, 어떤 식으로 움직이는 것이 최선인지 바로 파악할 수 있다면 정말 편하겠지만, 이는 생각보다 복잡하다.

그렇기 때문에 우리는 우리가 취할 수 있는 각각의 움직임들에 소요되는 좌,우 움직임의 횟수를 모두 확인하며 최솟값을 탐색할 것이다.

 

알고리즘 선택

그렇다면, 우리는 좌, 우 움직임의 최소 횟수를 구하기 위해 어떤 알고리즘을 사용할 수 있을까?

가장 먼저 생각할 수 있는 것이 DFS, BFS 등의 그래프 탐색을 이용한 경우의 수 탐색 알고리즘이다.

물론, DFS나 BFS로도 경우의 수를 탐색할 수 있으며, 구현 난이도는 비교적 쉬울 수 있다.

 

하지만, 두 방법은 조금씩 비효율 적인 측면이 있다.

 

먼저, DFS를 이용한 경우의 수 탐색 방법은 각각의 경우에 대해 끝까지 계산을 해야지 해당 경우의 최솟값을 구할 수 있다.

예를 들어, "AAAAAAAAK"의 경우, 왼쪽으로 한번만 이동하면 되기 때문에 좌,우 이동의 최솟값은 1이다.

하지만, 오른쪽으로의 탐색을 먼저 하기로 결심했다면, 오른쪽으로 시작해서 끝날 수 있는 모든, ( 그리고, 사실은 탐색할 필요가 없었던) 경우를 탐색한 다음에야 왼쪽으로의 탐색을 시작하게 된다.

 

이러한 문제점은 BFS 알고리즘을 선택한다면 해결할 수 있다. BFS 알고리즘은 현재 상태에서 선택할 수 있는 모든 상황을 병렬적으로 탐색하기 때문이다.

하지만, 이 BFS의 병렬적 탐색으로 발생할 수 있는 문제가 또 생긴다.

이번 문제는, 각각의 움직임에 대해 항상 오른쪽과 왼쪽이라는 두가지 선택지가 있기 때문에 단계를 진행할 때 마다 우리가 고려해야 하는 경우가 2^n 개로 늘어나는 것이다.

이를 해결하기 위한 별도의 해결 방법이 필요하다.

(만약, 현재 상태를 기억하기 위한 하나의 클래스를 만든다면, 그럭 저럭 손쉽게 해결할 수 있을 것이다.)

 

그렇다면, 어떤 방법으로 해결하는 것이 유리할까?

이번 문제에서는 투 포인터를 사용해 각각의 경우를 탐색하는 방법을 사용할 것이다.

그 전에, 이번 문제에서 우리가 탐색할 수 있는 좌,우 움직임을 조금 더 살펴보자.

"BCAAAAAAZK" 이름의 경우, "오, 왼, 왼, 왼"의 순서로 탐색하는 것이 최선이라고 했다.

이를 조금만 더 고민해 본다면, 방향이 오른쪽에서 왼쪽으로, 또는 왼쪽에서 오른쪽으로 바뀌는 경우는 한번 이하인 것이 최선의 경우에 해당한다는 것을 알 수 있다.

 

우리는 이제, 각 탐색의 경우에 대해서 다시 정방향 탐색과 역방향 탐색으로 분리하여 생각할 것이다.

이 때, 하나의 포인터는 정방향으로 탐색을 진행하는 경우의 마지막 탐색 위치를, 또 하나의 포인터는 역방향으로 탐색을 진행하는 경우의 마지막 탐색 위치를 저장해 둘 것이다.

즉, "BCAAAAAAZK" 이름에 대해서는 다음의 경우들을 탐색할 것이다.

• 0번째 인덱스 "B"까지 정방향으로 이동 하며 변경 하고, "1"번째 인덱스의 "C"까지 역방향으로 이동 하며 변경
• 1번째 인덱스 "C"까지 정방향으로 이동 하며 변경 하고, "8"번째 인덱스의 "Z"까지 역방향으로 이동 하며 변경
• 8번째 인덱스 "Z"까지 정방향으로 이동 하며 변경 하고, "9"번째 인덱스의 "K"까지 역방향으로 이동 하며 변경
• 9번째 인덱스 "K" 까지 모두 정방향으로 이동하며 변경

 

여기서 조심해야 할 것은, "정방향으로 1번째 인덱스까지, 역방향으로 8번째 인덱스까지 탐색을 한다." 라는 말이 "정방향으로 1번째 인덱스 까지 탐색을 한 이후, 역방향으로 8번쨰 인덱스까지 탐색을 한다" 라는 뜻이 되지는 않는다는 것이다.

같은 인덱스 정보에서도, "역방향으로 8번째 인덱스까지 탐색을 한 이후, 정방향으로 1번째 인덱스까지 탐색" 하는 경우가 중복하여 존재하기 때문에, 두가지 경우의 수를 모두 고려 해 주어야 한다.

 

이렇게, 문제를 풀어 나간 과정에 대한 설명을 끝냈다.

아래는 위의 설명에 대한 소스코드를 첨부한다.

 

소스 코드

public int solution(String name) {    
    int cost = 0;

    for(int i = 0; i<name.length(); i++){
        int diff = name.charAt(i) - 'A';
        if(diff > 13)
            diff = 26 - diff;
        cost += diff;
    }

    int front = 0;
    int end = front;
    while(end < name.length() && name.charAt(end) == 'A')
        end++;

    int minVerCost = 0;
    while(end < name.length()){
        int backDistance = name.length() - end;
        int verCost = front + backDistance;
        if(front < backDistance)
            verCost += front;
        else
            verCost += backDistance;
        if(minVerCost == 0)
            minVerCost = verCost;
        else if(minVerCost > verCost)
            minVerCost = verCost;

        front = end;
        end++;
        while(end < name.length() && name.charAt(end) == 'A')
            end++;
    }
    if(front < minVerCost)
        minVerCost = front;

    cost += minVerCost;

    return cost;        
}