[PG] 조이스틱 JAVA

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

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

완성해야할 이름 String name이 주어진다.

A를 name.length()만큼 이어붙인 문자열에서 name을 만들기 위해 필요한 최소 이동값을 반환해야한다.

 

1. 최초 커서는 첫 번째 칸에 위치한다. 좌 or 우 한 번의 이동으로 옆 칸으로 이동이 가능하다.

2. 커서가 위치한 문자를 위 or 아래 이동을 통해 변경할 수 있다. (ex : A위 -> B, A아래 -> Z)

 

 

 

풀이 1. (틀린 코드지만 정답처리됨)

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;

        // 문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만
        // 코드는 JAN -> AAA으로 만드는 식으로 짰다
        ArrayList<Boolean> check = new ArrayList<Boolean>(Arrays.asList(new Boolean[name.length()]));
        Collections.fill(check, Boolean.FALSE);
        for(int i = 0; i < check.size(); i++) {
            if(name.charAt(i) == 'A') {  // A인 것은 true, 나머지는 전부 false로 봤다
                check.set(i, true);
            }
        }

        int cursor = 0;  // 커서를 옮겨가며 진행
        while(check.contains(false)) {
            // 커서가 위치한 곳이 A가 아니라면 A로 만들어주면서 카운트
            if(check.get(cursor) == false) {
                int upCnt = name.charAt(cursor) - 'A';
                int downCnt = 25 - upCnt + 1;
                if(upCnt < downCnt) {  // 위, 아래 중 최소경로를 적용
                    answer += upCnt;
                }else {
                    answer += downCnt;
                }
                check.set(cursor, true);  // A로 만들어줌
            }

            // 커서를 왼쪽, 오른쪽 중 어디로 이동할 것인가?
            int left = cursor - 1, leftCnt = 1;
            int right = cursor + 1, rightCnt = 1;
            while(check.contains(false)) {  // A가 아닌 문자를 찾을 때까지 좌우 번갈아가며 검사
                // 인덱스 범위 벗어나는 이동에 대한 처리
                if(left == -1) {
                    left = name.length() - 1;
                }
                if(right == name.length()) {
                    right = 0;
                }

                // 양 옆의 문자를 한칸씩 확인하여 A가 아닌 것이 있다면 그쪽으로 이동
                // 한칸씩 번갈아가며 화인한다고 하더라도 그 한 칸을 왼,오 어느쪽부터 볼 것인지를 선택해야한다
                // 어떻게 선택해야할지 모르겠어서 그냥 오른쪽 먼저 검사하는 것으로 했다
                // ex : (B)(Cursor)(B) 일 때 오른쪽을 우선으로 이동
                if(check.get(right) == false) {
                    cursor = right;
                    answer += rightCnt;
                    break;
                }

                if(check.get(left) == false) {
                    cursor = left;
                    answer += leftCnt;
                    break;
                }

                left--; leftCnt++;
                right++; rightCnt++;
            }
        }

        return answer;
    }
}

(문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만 코드는 JAN -> AAA으로 만드는 식으로 짰다)

 

커서를 하나 두고 A가 아닌 곳을 찾아 이동해가며 문자를 변경했다.

 

커서가 위치한 곳에서 왼쪽, 오른쪽 방향으로 A가 아닌 문자가 가장 가깝게 위치한 곳을 다음 커서로 삼았다.

 

이때 커서 양 옆에 동일한 간격으로 A가 아닌 문자가 존재할 때 문제가 발생한다.

왼쪽, 오른쪽 어느 방향에 우선순위를 둬야할지 기준이 모호한 것이다.

잘 모르겠어서 그냥 에라 모르겠다 하고 오른쪽에 우선순위를 두고 풀었다.

 

정답처리가 되긴 했지만 결과적으로 틀린 코드이다. 프로그래머스의 테스트케이스가 부실해서 틀린 코드도 정답처리가 되어버렸다. 

 

(반례)

ABBAAAAAAAAAB 정답 7 -> 8 나온다

BABAAAAAAAAAAAABAAAB 정답 13 -> 15 나온다

 

 

 

풀이 2. (정답 코드)

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        ArrayList<Integer> ansList = new ArrayList<>();
        ArrayList<Character> cList = new ArrayList<>();
        for (int i = 0; i < name.length(); i++) {
            cList.add(name.charAt(i));
        }


        // 일단 위아래 이동부터
        int upDown = 0;
        for (int i = 0; i < cList.size(); i++) {
            char ch = cList.get(i);
            int upCnt = ch - 'A';
            int downCnt = 26 - upCnt;
            upDown += Math.min(upCnt, downCnt);
        }


        // 쭉 오른쪽
        int rightAns = 0, lastRightIndex = 0;
        for (int i = cList.size() - 1; i >= 0; i--) {
            if (cList.get(i) != 'A') {
                lastRightIndex = i;
                break;
            }
        }
        rightAns = lastRightIndex;
        ansList.add(upDown + rightAns);


        // 쭉 왼쪽
        int leftAns = 0, lastLeftIndex = 0;
        for (int i = 1; i < cList.size(); i++) {
            if (cList.get(i) != 'A') {
                lastLeftIndex = i;
                break;
            }
        }
        leftAns = cList.size() - lastLeftIndex;
        ansList.add(upDown + leftAns);


        // 오른쪽 가다가 왼쪽
        lastLeftIndex = 0;  // i보다 큰 인덱스 중에서 가장 왼쪽에 있는 A가 아닌 인덱스
        for (int i = 1; i < cList.size(); i++) {  // i : 방향전환점
            int leftRight = i * 2;  // i까지 이동했다 다시 [0]으로 돌아옴
            for (int j = i + 1; j < cList.size(); j++) { // lastLeftIndex 찾기
                if (cList.get(j) != 'A') {
                    lastLeftIndex = j;
                    break;
                }
            }
            leftRight += cList.size() - lastLeftIndex;
            ansList.add(upDown + leftRight);
        }


        // 왼쪽 가다가 오른쪽
        lastRightIndex = 0;
        for (int i = 1; i < cList.size(); i++) {
            int leftRight = (cList.size() - i) * 2;  // i까지 이동했다 다시 [0]으로 돌아옴
            for (int j = i - 1; j >= 1; j--) {
                if (cList.get(j) != 'A') {
                    lastRightIndex = j;
                    break;
                }
            }
            leftRight += lastRightIndex;
            ansList.add(upDown + leftRight);
        }

        answer = Collections.min(ansList);
        return answer;
    }
}

(문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만 코드는 JAN -> AAA으로 만드는 식으로 짰다)

 

일단 좌우 이동을 신경쓰기 전에 문자를 변경하는 데 사용되는 위아래 이동부터 한꺼번에 먼저 체크했다.

 

그 이후 좌우 이동을 체크했는데, 이동 가능한 모든 경로에 대한 이동수를 저장하여 그 중 최소값으로 정답을 찾아냈다.

 

아래와 같은 네 가지 경로로 이동이 가능하다.

1. 처음부터 쭉 오른쪽으로만 가기

2. 처음부터 쭉 왼쪽으로만 가기

3. 처음엔 오른쪽으로 가다가 중간에 꺾어서 왼쪽으로 가기 

4. 처음엔 왼쪽으로 가다가 중간에 꺾어서 오른쪽으로 가기

 

1, 2번 경우의 이동 수는 그냥 인덱스를 계산하여 쉽게 구할 수 있다.

 

문제는 3, 4번 경우인데, "중간에 꺾어서"의 중간점을 어디로 잡아야 하는지였다.

 

이것도 그냥 다 해봤다. ( [1] ~ [size()-1] 각각의 점을 꺾는 포인트로 잡고 모든 경우를 계산했다.)

주어지는 문자열의 최대 길이가 20밖에 안 되기 때문에 이 방법을 사용할 수 있었다.

 

 

시간을 너무 많이 들였다... 이렇게까지 시간을 들여서 푸는 게 의미가 있나 싶다.

솔직히 코드도 막무가내 구현 식으로 엉망인 것 같다;