프로그래머스 - 조이스틱 (sol.java)

◎문제 링크

programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

---

◎문제 파악

그리디 문제로 분류되어있는 조이스틱 문제는 두 가지 문제의 합으로 생각할 수 있다.

1.(위, 아래) 'A'에서 'B' 방향으로 가야 최소 방향인가 'Z' 방향으로 가야 최소 방향인가

2.(오른쪽, 왼쪽) 커서의 위치가 어디로 가야 최소 횟수로 가는 방향인가

 

 

---

◎1번 sol)

 

'A'의 ASCII 코드 값은 65이다.

'Z'의 ASCII 코드 값은 90이다.

 

A B C D ..... '중간값' .... X Y Z

알파벳은 26개이므로, A에서 위로 13번 갔을 때 나오는 문자와 A에서 아래로 13번 갔을때 나오는 문자가 같아야 하며, 그 문자(중간값)는 ASCII 코드가 78인 'N'이다.

 

그러므로, 어떤 문자의 ASCII 코드값이 78보다 작거나 같으면 위로

ASCII코드 값이 78보다 크거나 같으면 아래로 조이스틱을 움직이면 된다.

 

  //문자 변경(위아래 조이스틱)파트
            if((int)name.charAt(j)<=78){
                answer = answer + (int)name.charAt(j) - 65;
                // 'N'보다 작거나 같은 ASCII코드 값을 가지면 다음 알파벳(위방향 커서)로 옮겨가는게 최소이동
            }
            else{
                answer = answer + 91 - (int)name.charAt(j);
                // 'N'보다 큰 ASCII코드 값을 가지면 이전 알파벳(아래방향 커서)로 옮겨가는게 최소이동             
            }

 

---

◎2번 sol)

 

2번 문제는 간단히 오른쪽으로 가야 한다. 왼쪽으로 가야 한다고 한 번에 정하는 문제가 아니다.

 

ex1) "BAAAB"일 경우

① index 0의 문자를 B로 바꾼다. (+1)

② 커서를 왼쪽(index 4)으로 한 칸 옮긴다. (+1)

③ index 4의 문자를 B로 바꾼다. (+1)

최소 횟수: 3

 

이 경우에는 한번 정한 커서 변경 방향으로 계속 가면 된다.

 

ex2)   

String	A	B	A	A	A	A	A	A	A	B	B
Index	0	1	2	3	4	5	6	7	8	9	10

① 커서를 오른쪽(index 1)으로 한 칸 옮긴다. (+1)

② index 1의 문자를 B로 바꾼다. (+1)

③ 커서를 왼쪽(index 0)으로 한칸 옮긴다. (+1)

④ 커서를 왼쪽(index 10)으로 한칸 옮긴다. (+1)

⑤ index 10의 문자를 B로 바꾼다. (+1)

⑥ 커서를 왼쪽(index 9)으로 한칸 옮긴다. (+1)

⑦ index 9의 문자를 B로 바꾼다. (+1)

최소 횟수: 7

 

이 경우에는 위의 경우와 다르게 커서를 오른쪽으로 옮겼다가 다시 왼쪽으로 옮겨야 한다.

 

∴ 각 상황에 맞추어 왼쪽으로 가는 게 이득일지 오른쪽으로 가는게 이득인지 판단하여 Greedy 하게 해결하자

 

0

1

2

3

4

5

 

1. 현재 커서의 위치인 index 0을 1번 sol)의 방식으로 알파벳 변경한다.

2. "오른쪽 방향으로 갔을 때  'A'가 아닌 문자가 나올 때까지 옮긴 커서의 이동거리"(right)와

   "왼쪽 방향으로 갔을때  'A'가 아닌 문자가 나올때까지 옮긴 커서의 이동거리"(left)를 비교하여

   더 짧은 방향으로 greedy 하게 움직인다.

3. 모든 문자가 알맞게 변경될 때까지 반복한다.

 

※ 3. 모든 문자가 알맞게 변경되었는지 알기 위해서, 1번에서 변경된 알파벳은 잘 변경되었다는 의미로 'A'로 변경하고,

right나 left가 문자열의 전체 길이와 같아지면, 모든 문자가 'A'인 것으로 판단한다.

 

전체 코드:

class Solution {
    public int solution(String name) {
        int answer = 0;
        int k;// 모든 문자가 'A'인지 확인하는 변수
        int j = 0; //커서의 인덱스 변수
    
        
        while(true){
            
            //문자 변경(위아래 조이스틱)파트
            if((int)name.charAt(j)<=78){
                answer = answer + (int)name.charAt(j) - 65;
                // 'N'보다 작거나 같은 ASCII코드 값을 가지면 다음 알파벳(위방향 커서)로 옮겨가는게 최소이동
            }
            else{
                answer = answer + 91 - (int)name.charAt(j);
                // 'N'보다 큰 ASCII코드 값을 가지면 이전 알파벳(아래방향 커서)로 옮겨가는게 최소이동             
            }
            name = name.substring(0, j) + 'A'+ name.substring(j+1);
            System.out.println(name);
            // 변경한 문자를 'A'로 바꾸어 문자 변경이 완료 되었음을 알림
            
            
            
            //커서변경(오른쪽 왼쪽 조이스틱 파트)
            int right, left;
            right = 0;
            left = 0;
            //현재 커서위치에서 오른쪽 방향으로 갔을때, 'A'가 아닌 문자가 나올때까지 옮긴 커서의 이동거리:right
            //현재 커서위치에서 오른쪽 방향으로 갔을때, 'A'가 아닌 문자가 나올때까지 옮긴 커서의 이동거리:left
            
            int tmp=j; //tmp는 변경커서
            
            while(right<name.length()){
                if(name.charAt(tmp)==65){//변경커서에 해당하는 문자가 'A'이면
                    if(tmp <name.length()-1){
                        tmp++;
                    }
                    else{
                        tmp = 0;
                    }
                    right++; //right에 1을 더해준다.
                }
                else{
                    break;
                }
            }
            
            tmp = j; //변경커서 초기화
            
            while(left<name.length()){
                if(name.charAt(tmp)==65){//변경커서에 해당하는 문자가 'A'이면
                    if(tmp >0){
                        tmp--;
                    }
                    else{
                        tmp = name.length()-1;
                    }
                    left++;//left에 1을 더해준다.
                }
                else{
                    break;
                }
            }
            
            if(left == name.length() || right == name.length()){
                break; //left또는 right가 name.length()와 같다는것은 모든 문자가 'A'라는 뜻이므로, 루프를 끝낸다.
            }
            else{
                if(right<=left){ // 오른쪽으로 이동하는게 왼쪽으로 이동하는것보다 적거나 같은 이동횟수를 가지면 오른쪽으로 이동
                    if(j+right<=name.length()-1){
                        j= j+right;
                    }
                    else{
                        j = j+right-name.length();
                    }
                    answer = answer +right; 
                }
                else{// 왼쪽으로 이동하는게 오른쪽으로 이동하는것보다 적은 이동횟수를 가지면 왼족으로 이동
                    if(j -left >=0){
                        j = j-left;
                    }
                    else{
                        j = j-left+name.length();
                    }
                    answer = answer +left;
                }
            }
            
        }
        return answer;
    }
}

 

이렇게 코드를 짜면, programmers 문제는 통과할 수 있다.

---

◎그리디 문제

하지만 

String	A	B	B	A	A	A	A	A	A	A	B
Index	0	1	2	3	4	5	6	7	8	9	10

ex2)에서 index2와 index9만 변경한 위의 경우에 최소 이동 횟수는

 

① 커서를 왼쪽(index 10)으로 한 칸 옮긴다. (+1)

② index 10의 문자를 B로 바꾼다. (+1)

③ 커서를 오른쪽(index 0)으로 한칸 옮긴다. (+1)

④ 커서를 오른쪽(index 1)으로 한칸 옮긴다. (+1)

⑤ index 1의 문자를 B로 바꾼다. (+1)

⑥ 커서를 오른쪽(index 2)으로 한칸 옮긴다. (+1)

⑦ index 2의 문자를 B로 바꾼다. (+1)

최소 횟수: 7

 

하지만,  전체 코드의 70번째 줄 코드를 보면

 if(right<=left){ // 오른쪽으로 이동하는게 왼쪽으로 이동하는것보다 적거나 같은 이동횟수를 가지면 오른쪽으로 이동

오른쪽으로 이동하는 게 왼쪽으로 이동하는 것보다 적거나 같은 이동횟수를 가지면 오른쪽으로 이동하므로, ①에서 커서를 왼쪽으로 이동하는게 최소 이동 횟수임에도 불구하고 오른쪽을 먼저 탐색한다.

그러므로,

① 커서를 오른쪽(index 1)으로 한 칸 옮긴다. (+1)

② index 1의 문자를 B로 바꾼다. (+1)

③ 커서를 오른쪽(index 2)으로 한칸 옮긴다. (+1)

④ index 2의 문자를 B로 바꾼다. (+1)

⑤ 커서를 왼쪽(index 1)으로 한칸 옮긴다. (+1)

⑥ 커서를 왼쪽(index 0)으로 한칸 옮긴다. (+1)

⑦ 커서를 왼쪽(index 10)으로 한칸 옮긴다. (+1)

⑧ index 10의 문자를 B로 바꾼다. (+1)

이동 횟수: 8

 

코드를 실행하면 이동횟수 8이 나오게 되어 오류가 생긴다.

∴이 문제는 프로그래머스에서는 그리디 문제로 분류되어있지만, 부분해의 합이 최적해가 되지 않으므로 사실상 그리디 문제라고 할 수 없다. 그리디 문제라면, right <=left이든, right <left 이든 해가 같아야 한다. 오히려, 문자 'A'로 구분되는 커서 방향에 따른 완전 탐색 문제여야 할 것이다. 완전탐색 풀이는 아래의 다른 사람의 풀이로 대체하겠다.

 

---

◎다른 사람의 풀이

class Solution {
    public int solution(String name) {
        int answer = 0;
        
        
        //알파벳 변경
        int[] diff={0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1};
        //기본문자인 'A'에서 각 알파벳이 얼마나 떨어져있는지 나타내는 int배열
        for(char c:name.toCharArray())
            answer+=diff[c-'A'];
        //각 알파벳을 변경하기 위한 이동횟수를 answer에 누적

        
        //커서 변경
        int length=name.length();
        int min=length-1;

        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));
        }

        return answer+min;
    }
}

1.(위, 아래) 'A'에서 'B' 방향으로 가야 최소 방향인가 'Z' 방향으로 가야 최소 방향인가

2.(오른쪽, 왼쪽) 커서의 위치가 어디로 가야 최소 횟수로 가는 방향인가

의 두 가지 문제를 while문 안에 넣어서 차례차례 1번과 2번을 함께 해결했던 나의 풀이와 다르게, 1번과 2번 문제를 이 코드는 각각 처리했다,

 

알파벳 변경 부분(6~11줄)에서는 diff배열을 활용하여, 'A'에서 다른 문자가 되려면 얼마나 이동해야 하는지를 계산하여 for문 람다식에 넣어 한번에 처리하였다.

 

커서 변경 부분(14~26줄)은 2번 문제에 대해 더 깊게 파악하였다.

최소 횟수를 찾는 방법은

'A'가 아닌 문자로 무조건 커서가 가야 한다.

=> 'A'인 곳으로는 커서가 가지 않아도 된다.

=> 'A'로만 이루어진 문자열을 지나지 않은 것 중 하나가 최소 횟수이다.

 

ex 1) 

"BAABBBAAAAA"

'A'로만 이루어진 가장 긴 문자열을 지나지 않은 게 최소 횟수이므로, 'A'로만 이루어진 문자열 'AA'와 'AAAAA'에 대하여, 'AA'를 지나가는 경우:

index 변경: 0-1-2-3-4-5

index 변경 횟수: 5

 

'AAAAA'를 지나가는 경우:

index 변경: 0-10-9-8-7-6-5-4-3

index 변경 횟수: 8

 

∴'AA'를 지나가는 것이, 'AAAAA'를 지나가는 것보다 이득이다.

 

ex 2)

"BABAB"

'A'로만 이루어진 가장 긴 문자열을 지나지 않은게 최소횟수이므로 'A'로만 이루어진 문자열 '앞쪽 A'와 '뒤쪽 A'에 대하여, 

'앞쪽 A'를 지나는 경우:

index 변경: 0-4-0-1-2

index 변경 횟수: 4

 

'뒤쪽 A'를 지나는 경우:

index 변경: 0-4-3-2

index 변경 횟수: 3

 

∴'뒤쪽 A'를 지나는 것이 이득이다.

 

코드를 더 자세히 살펴보면,

  //커서 변경
        int length=name.length();
        int min=length-1; // 모든 문자열을 그냥 지나가는 경우 이동횟수
 
        for(int i=0;i<length;i++){
            int next=i+1;
            while(next<length && name.charAt(next)=='A'){
                next++;
            } 
            //i의 오른쪽에 'A'로 이루어진 문자열의 길이 찾기
            
            min=Math.min(min,i+ length - next + Math.min(i,length-next));
            //i+length-next: 'A'로 이루어진 문자열을 제외한 나머지 문자열 길이 -1
            //Math.min(i,length-next): 방향을 바꾸었을 때 중복되어 지나가는 이동길이
        }

7번째 줄의 while 문으로, 'A'로 이루어진 문자열의 길이를 찾는다.

그리고 12번째 줄의 Math.min을 두 번 사용하여, 현재 찾은 최소 이동거리 값(min)과

i+length-next+Math.min(i, length-next)를 비교한다.

 

i+ length-next: ( i번째 인덱스 오른쪽에 있는, 'A'로 이루어진 문자열을 제외한 나머지 문자열 길이-1)

Math.min(i, length-next): 방향을 바꾸었을 때 중복되어 지나가는 이동길이