프로그래머스 - 조이스틱

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

프로그래머스

 

 

 

 

 

문제

• 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
  • ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
• 조이스틱을 각 방향으로 움직이면 아래와 같습니다.
  • ▲ - 다음 알파벳
  • ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
  • ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
  • ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
• 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하기

 

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

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

 

 

제한 사항

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

 

 

 

 

 

풀이1 : 그리디 (=틀린 풀이)

처음에는 알고리즘 풀이법이 탐욕법(Greedy)로 분류가 되어있어서 그리디한 방법으로 풀었다.

 

• int형의 배열에 각 문자별로 A에서 해당 문자가 되기 위해 조작해야 하는 횟수를 저장한다.
• 그리디한 방법으로 (현재 위치에서 해당 숫자까지의 이동 횟수 + 조작 횟수)가 작은 것부터 조작한다.
• 조작된 위치는 0으로 바꿔준다.
• 문자를 다 조작할 때까지 반복한다. 

 

 

 

 

 

실패 코드

class Solution {
    public int solution(String name) {
        int[] times = new int[name.length()]; //해당 문자가 되기 위해서 조작해야 하는 횟수
        int count = 0; //조작된 문자 수
        
        for(int i = 0; i < name.length(); i++) {
            char ch = name.charAt(i);
            
            int up = ch - 65; //위로 올렸을 때 횟수
            int down = 90 - ch + 1; //아래로 내렸을 때 횟수
            
            times[i] = Math.min(up, down);
            
            if(times[i] == 0) { //이미 A이면 조작된 문자 개수에 올리기
                count++;
            }
        }
        
        //구현
        int answer = 0; //정답 : 조작 횟수
        int cursor_now = 0; //커서 위치
        
        while(count < name.length()) {
            // for(int n : times) {
            //     System.out.print(n + " ");
            // }
            
            //양옆으로 이동해서 갈 수 있는 가장 가까운 조작 안된 위치 구하기
            int cursor_left = cursor_now;
            int left_count = 0;
            while(true) { //0(조작 완료)이 아닐 때까지
                if(times[cursor_left] != 0) break;
                
                cursor_left--; //왼쪽으로 이동
                left_count++;
                
                if(cursor_left == -1) { //끝에 도달하면
                    cursor_left = name.length() - 1; //끝으로
                }
            }
            
            int cursor_right = cursor_now;
            int right_count = 0;
            while(true) { //0(조작 완료)이 아닐 때까지
                if(times[cursor_right] != 0) break;
                
                cursor_right++; //오른쪽으로 이동
                right_count++;
                
                if(cursor_right == name.length()) { //끝에 도달하면
                    cursor_right = 0; //처음으로
                }
            }
            
            // System.out.print("현재: " + cursor_now + " 왼쪽: " + cursor_left + " 오른쪽: " + cursor_right);
                
            //현재 위치 ~ 해당 위치까지 이동 횟수 + 조작 횟수 구하기
            int left = left_count + times[cursor_left];
            int right = right_count + times[cursor_right];
            
            //조작 횟수가 작은 위치로 이동
            if(left < right) {
                // System.out.println(" 왼쪽 조작횟수: " + left_count + "+" + times[cursor_left]);
                cursor_now = cursor_left;
                answer += left; //조작 횟수 증가
            } else {
                // System.out.println(" 오른쪽 조작횟수: " + right_count + "+" + times[cursor_right]);
                cursor_now = cursor_right;
                answer += right; //조작 횟수 증가
            }
            
            times[cursor_now] = 0; //조작 완료
            
            count++;
        }
        
        return answer;
    }
}

 

 

 

 

 

실패 결과

 하지만 이렇게 풀었더니 모든 TC를 통과하지 못하여 59점이 나왔다. 게시판을 보니 예전에는 그리디로 풀렸다고 하지만, TC가 추가되면서 문제가 그리디로는 풀 수 없게 바뀐 것 같다고 한다. 그리디라는 카테고리에 속지 말자!

 

 

 

 

 

게시판에서 찾은 반례가 있다.

"ABAAABB”인 경우, 처음 위치인 0에서 왼쪽이나 오른쪽으로 모두 1회 이동이 가능하다.

하지만 왼쪽으로 가게 될 경우 이후, 왼1, 왼1, 오3으로 총 5회,

오른쪽으로 시작할 경우 이후, 오1, 왼2, 왼1로 총 4회가 나오게 된다.

 

그리디한 방법이 적용되지 않는다.

 

 

 

 

 

풀이2 : 부르트포스, 투포인터

 그럼 그리디가 아니라 모든 경우의 수를 확인하는 부르트포스(완전탐색) 방식으로 풀어야 모든 TC를 통과할 수 있다.

 

 그리고 사실 조작 횟수에 영향을 주는 것은 위아래로 움직이는 횟수가 아니라 좌우로 움직이는 횟수이다. 위 아래로 조작하는 횟수는 '위로 조작했을 때와 아래로 조작했을 때의 최솟값'으로 정해져있기 때문이다. 그러므로 위아래로 움직이는 횟수는 따로 계산하고, 좌우로 움직이는 횟수의 최솟값만 신경을 쓰면 된다.

 

 

 

좌우로 움직이는 경우의 수는 다음과 같다.

• 방향 전환 없이 오른쪽으로 계속 움직이는 경우
• 방향 전환 없이 왼쪽으로 계속 움직이는 경우
• 오른쪽으로 이동하다가 왼쪽으로 방향을 전환해 움직이는 경우
• 왼쪽으로 이동하다가 오른쪽으로 방향을 전환해 움직이는 경우

 

 

 

 

한방향으로 갔을 때의 값은 (Name의 길이 - 1)로, 최대값이 된다.

하지만 위의 TC의 경우에는, 중간에 방향 전환을 하게 되는 경우에는 더 적은 조작 횟수로 가능하다.

 

오른쪽으로 이동하게 되는 경우, A를 만나면 방향 전환을 해서 왼쪽으로 가게 된다.

그렇다면, 총 조작 횟수는 (시작점부터 오른쪽으로 갈 때의 길이 * 2) + (시작점에서 왼쪽으로 갈 때의 길이)가 된다.

 

마찬가지로 왼쪽으로 이동하게 되는 경우, A를 만나면 방향 전환을 해서 오른쪽으로 가게 된다.

그렇다면, 총 조작 횟수는 (시작점부터 왼쪽으로 갈 때의 길이 * 2) + (시작점에서 오른쪽으로 갈 때의 길이)

 

 

 

 

그리고 모든 경우의 수를 알려면, 시작점을 0부터 Name의 마지막 인덱스까지 최소 조작 횟수를 구하면 된다.

시작점과 끝점이 있고, 시작점과 끝점의 인덱스를 늘려가면서 푸는 방식이 투포인터와 유사하다.

 

• 시작점을 0부터 마지막 인덱스까지 모두 두고
• 시작점을 기준으로 3가지 경우의 수에 대해 각각 조작 횟수를 구한다.
• 3가지 경우 중, 최소 조작 횟수가 시작점으로부터의 이동횟수가 된다.
• 모든 시작점에 대해 최소값을 구하여 갱신해준다.

 

 

 

 

 

코드

class Solution {
    public int solution(String name) {
        int answer = 0; //정답 : 조작 횟수
        int length = name.length();
        int move = length - 1; //좌우 움직임 수 : 최대는 길이 - 1
        
        for(int start = 0; start < length; start++) {
            //상하 이동 횟수 구하기
            char ch = name.charAt(start);
            int up = ch - 'A'; //위로 올렸을 때 횟수
            int down = 'Z' - ch + 1; //아래로 내렸을 때 횟수
            
            answer += Math.min(up, down);
            
            //좌우 이동 횟수 구하기
            int end = start + 1; //다음 A가 아닌 문자의 인덱스
            
            while(end < length && name.charAt(end) == 'A'){ //A가 아닌 문자나오기 전까지 탐색
                end++;
            }
            
            int l1 = start; //앞 부분의 길이
            int l2 = length - end; //뒷 부분의 길이

            //정방향으로 갔을 때와
            //정방향 갔다가 역방뱡 가는 경우, 역방향 갔다가 정방향 가는 경우 비교
            move = Math.min(move, l1 + l2 + Math.min(l1, l2));      
        }
        
        return answer + move;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

참고

• https://blog.naver.com/gkswlcjs2/223020408078

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

 

• https://velog.io/@jeeseob5761/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1

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