[프로그래머스 42860번] 조이스틱 + 테스트 케이스

문제

번호

내용

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

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

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

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

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

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

입출력 예

name	return
JEROEN	56
JAN	23

언어

JAVA

풀이

'이게 왜 Greedy 문제인가...'라는 고민이 많이 되었다.

테스트 케이스 중 일부가 이리저리 계속해서 실패하는 탓에 오래 걸린 문제이기도 했다. 이리저리 따져야하는 조건이 많음에도 그저 쑤셔넣기로 해서 계속 테스트 케이스 오류가 발생하였다. 반성이 되는 문제이기도 했고 솔직히 열받는 문제이기도 했다.

테스트 케이스 오류

처음에는 10번, 11번 테스트 케이스가, 이후에는 3번 테스트 케이스가, 그 후에는 5번 테스트 케이스가 문제였다.

10번, 11번 테스트 케이스의 경우 왼쪽으로 가는 경우를 제대로 처리하지 못하였을 때(어떤 경우에 왼쪽으로 가야 하는가)와 연속된 A를 처리하지 못했을 때('A'가 포함되어있는 경우 뿐만 아니라 "AAA" 등이 포함되어 있는 경우) 발생하였다.

3번 테스트 케이스는 맨 마지막에 연속되는 A가 나왔음에도 좌/우 컨트롤이 포함되는 경우(BBAB에서는 좌/우 컨트롤이 2가 되지만 BBBAAA에서 좌/우 컨트롤 수가 5가 되는 경우)에 발생하였다.

5번 테스트 케이스는 마지막에 연속되는 A + 알파가 나왔을 때 그 경우를 제대로 처리하지 못하고 알파 부분을 무시해서 발생하였다.

테스트 케이스

아래는 오류 해결을 위해 적용했던 테스트 케이스이다.

name	result	설명
"AAAAAA"	0	문자열 전체가 A로만 이뤄진 경우 좌/우 컨트롤 수 처리
"AAAACB"	5	왼쪽으로만 가는 경우
"AABAAAAAAABBB"	11	오른쪽으로 갔다가 왼쪽으로 가야하는 경우
"CANAAAAANAN"	48	오른쪽으로 갔다가 왼쪽으로 가야하는 경우
"ABAAAAABAB"	8	오른쪽으로 갔다가 왼쪽으로 가는 경우
"BBBAAB"	9	뒤에 연속적인 A 문자열 + 알파가 왔을 때 좌/우 컨트롤 수 처리
"CAAAAAA"	2	뒤에 연속적인 A 문자열이 왔을 때 좌/우 컨트롤 수 처리

문제 해결

좌/우 컨트롤 수와 상/하 컨트롤 수의 합을 구하는 문제로 볼 수 있다.

상/하 컨트롤 수는 구하기 쉽다.

처음은 A로 시작해서 위로 올리면 A→B→C 순으로 증가하고, 아래로 내리면 A→Z→Y 순으로 감소한다. 즉 어떤 문자가 있다면 그 문자가 A 와 Z 중 어디와 가까운지 비교하면 된다. 아스키코드를 이용해서 비교하면 편하다.

문제는 좌/우 컨트롤 수이다. 커서를 이동하는데, 문자열의 구성에 따라 이동하는 수가 달라지기 때문에 고려해야할 상황도 많고 까다롭다.

왼쪽 컨트롤을 하는데 앞의 문자가 A가 아닌 다른 문자일 경우 진행 → 상/하 변경 → 다시 뒤로 돌아온 후 좌로 진행 하는 과정을 거쳐야 한다. 이는 진행했던 문자를 되돌아온다는 불필요한 과정이 있기 때문에 결국 최적이 되지 못한다. 그렇기에 좌 컨트롤이 발생하는 경우는 A를 만났을 때이다.

이를 고려해서 좌/우 이동하는 방법을 나눠보면 크게 3가지(세부 4가지) 상황이 나온다.

오른쪽으로만 진행하는 경우 : 도중에 왼쪽으로 이동하는 것 보다 오른쪽으로 계속 이동하는 것이 최적일 경우이다.
왼쪽 진행이 포함되어 있는 경우
- 왼쪽으로만 진행하는 경우 : 오른쪽으로 이동하는 것 보다 처음부터 왼쪽으로 이동하는 것이 최적일 경우이다.
- 오른쪽으로 갔다가 왼쪽으로 진행하는 경우 : 중간에 연속되는 A가 나오고 그 앞/뒤로 처리하는 것이 최적일 경우이다.
진행하지 않는 경우 : 전체 문자열이 A로만 이뤄진 경우이다.

진행하지 않는 경우는 간단하다. 나머지 경우의 기준은 무엇일까? 수학적으로 계산해보았다.

Input으로 들어온 문자열인 <pre>name</pre>이 다음 그림과 같이 구성되어 있다고 하자.

오른쪽으로만 진행하는 경우의 좌/우 컨트롤 수는 $(a-1) + x + b$이다. 처음 문자는 커서 이동 없이 변경 가능하기 때문에 $-1$이 발생하였다.

왼쪽 진행이 포함된 경우의 좌/우 컨트롤 수는 $2 \times (a-1) + b$이다.

우선, 오른쪽 컨트롤을 이용해서 연속된 A 문자열이 나오기 전까지 진행해야 한다.($a-1$)
이후, 연속된 A 이후의 문자열을 처리하기 위해 왼쪽 컨트롤을 이용해서 다시 처음부분으로 돌아가야 한다.($a-1$)
이제는 왼쪽 컨트롤만 이용해서 연속된 A 이후의 문자를 처리한다.($b$)
따라서 위 과정의 합은 $2 \times (a-1) + b$이다.

위의 과정으로 인해 오른쪽으로만 진행하는 것 보다 왼쪽으로 진행하는 것이 유리한 조건은 다음과 같다.

$왼쪽 진행이 포함된 경우 좌/우 컨트롤 수 < 오른쪽으로 진행할 때 좌/우 컨트롤 수$

→ $2 \times (a-1) + b < (a-1) + x + b$

→ $2a + b - 2 < a + b + x - 1$

∴ $a < x + 1$

따라서 $a < x + 1$ 일 때 왼쪽 진행이 포함되어야 한다. 이를 이용해서 좌/우 컨트롤 조건을 세우고 코드를 작성하면 된다.

코드 설명

코드의 진행 과정은 다음과 같다.

왼쪽 진행을 포함할 것인지 판단
상/하 컨트롤 수 계산
좌/우 컨트롤 수 계산

위에서 구한 조건($a < x + 1$)을 이용해서 왼쪽 진행을 포함할 것인지를 판단한다. <pre>index_a > -1</pre>이라는 조건은 문자열에 'A'를 하나도 포함하지 않을 수도 있기 때문이다.

연속된 A가 여러 곳 나올 수도 있는데, 좌/우 컨트롤 수를 최소로 하기 위해서는 위 조건을 충족하고 연속된 A의 개수가 최대일 때이다. 이를 위해서 연속된 A의 개수를 <pre>list_a</pre>에 담는다. 이후 List의 <pre>sort()</pre>을 이용해서 내림차순으로 정렬한다. 그리고 조건을 만족하는지를 확인한다.

상/하 컨트롤 수의 계산은 간단하다. 해당 문자가 'A'와 'Z' 중 가까운 곳까지의 거리를 판단하면 된다. 단, 'Z'가 더 가까울 경우 A에서 Z까지 이동하는 데 아래 컨트롤이 한번 필요하므로 이를 고려해야 한다. 때문에 <pre>i - 'A'</pre>와 <pre>'Z' - i</pre>을 비교하는 것이 아닌 <pre>'Z' - i + 1</pre>을 비교하는 것이다.

이후에는 제일 까다로웠던... 좌/우 컨트롤 수를 계산해야한다.

이는 위에서 왼쪽을 포함해야하는지 판단한 수식을 이용하였다. 만약 왼쪽이 포함되어 있다면 $2 \times (a-1) + b $이고, 그렇지 않다면 $(a-1) + x + b$이다.

자세한 코드 내용은 주석으로 작성하였다.

코드

import java.util.*;

class Solution {
        public int solution(String name) {
        int answer = 0;
        int continue_a = 0;		// 연속된 A의 개수
        int index_a = name.indexOf('A');// 연속된 A가 시작하는 위치
        boolean reverse = false;	// 왼쪽이 포함되어 있는지 여부
        List<Integer> list_a = new ArrayList<>();

        if(index_a > -1) {
            for (int i = 0; i < name.length(); i++) {
                if(continue_a > 0 && name.charAt(i) > 65) {
                    list_a.add(continue_a);
                    continue_a = 0;
                }
                else if(name.charAt(i) == 65) continue_a++;
            }

            list_a.sort(Comparator.reverseOrder());
            while(!list_a.isEmpty()) {
                int temp = list_a.remove(0);
                if(temp == continue_a) {
                    index_a = name.indexOf("A".repeat(temp), index_a+1);
                }
                else {
                    index_a = name.indexOf("A".repeat(temp));
                    continue_a = temp;
                }

                if(index_a < continue_a + 1) {
                    reverse = true;
                    break;
                }
            }
        }

        // 위/아래 횟수 계산
        for(char i : name.toCharArray()) {
            answer += Math.min(i-'A', 'Z'-i+1);
        }

        // 좌/우 횟수 계산
        // 왼쪽으로 가는 것이 포함되어 있는 경우
        if(reverse) {
            // 오른쪽으로 갔다가 왼쪽으로 가는 경우
            if(index_a > 0) {
                answer += name.length() + index_a - continue_a - 2;
            }
            // 쭉 왼쪽으로 가는 경우
            else answer += name.length() - index_a - continue_a;
        }
        // 오른쪽으로만 가는 경우
        else {
            if(index_a + continue_a == name.length()) {
                // 맨 마지막에 A가 있을 때 : continue_a
                answer += name.length() - 1 - continue_a;
                // 전부 A
                if(answer < 0) answer = 0;
            }
            else {
                answer += name.length() - 1;
            }
        }

        return answer;
    }

}

'Etc > 문제 풀이' 카테고리의 다른 글

[백준 10448번] 유레카 이론 (0)	2021.09.03
[백준 2231번] 부분합 (0)	2021.09.02
[프로그래머스 42862번] 체육복 (0)	2021.02.21
[프로그래머스 42842번] 카펫 (0)	2021.02.21
[프로그래머스 42839번] 소수찾기 (0)	2021.02.20

[프로그래머스 42860번] 조이스틱 + 테스트 케이스