[알고리즘] 프로그래머스 조이스틱 -그리디-

 

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

프로그래머스

 

 

첫번째로 조이스틱 문제를 잘 못이해하여 다음과 같은 로직을 세워서 완벽하게 풀었으나 당연히 문제 설명과 달라서 오답이나왔다. 

밑과 같이 푼 이유는 위아래 이동은 알파벳 A->B, B->A 이런걸 의마하고 왼쪽 오른쪽 이동은 A로 한방에 가기 Z로 한방에 가기를 의마하는 줄 알았다. 실수...

1. 같은 알파벳인경우 이동 X
2. 시작지가 A Z 인 경우
3. 목적지가 A와 Z인 경우 한번만 움직이면됨 ( +1 ) (시작지가 A,Z인 경우는 2번에서 해결)
4. 현재알파벳과 목적지 알파벳 뺄셈한 절댓값 
vs A와 목적지 뺼셈한 절댓값(A로 가는거 +1 해줘야함, 원래 A였던 경우는 +1 안해도됨)
 vs Z와 목적지 뺼셈한 절댓값(Z로 가는거 +1 해줘야함, , 원래 Z였던 경우는 +1 안해도됨)

 

 

 

 

그담 문제를 이해하고 위아래는 해당 위치의 알파베이동 왼쪽오른쪽은 옆에 있는 알파벳 즉 배열 인덱스 이동인걸 알고 풀었다.

풀기전에 다음과 같이 정리 후 코드를 짰다.

1. 아무리 길어도 문자 최고길이 만큼 반복문돌리면됨
2. 첫문자부터 A인 경우 및 A아닌 경우 처리
3. 현재 인덱스에서 A가 아닌 문자에 왼쪽으로 이동하는게빠른지 오른쪽으로 이동하는게 빠른지 확인 (
4. 3번의 경우에 0인덱스에서 왼쪽으로가면 (문자열길이 -1) 인덱스가 되고 (문자열길이-1) 인덱스에서
오른쪽으로가면 0인덱스 됨을 유의 => 상하 이동도 마찬가지 A에서 Z로 한번에 갈 수 있음
5. 현재 인덱스 업뎃되야하고 조이스틱움직일 때마다 계산해서 결과에 더해줘야함

 

문제를 굉장히 더럽게 풀었다.

주석만 추가해서 올린 코드는 다음과 같다.나중에 코드정리좀 해볼까한다.

 

전체 코드는 다음과 같다. (String은 특정 인덱스 값을 replace할 수 없었다. StringBuilder만 가능하다. 그래서 StringBuilder를 사용해서 처리된 문자열은 A로 바꿔주면서 그리디를 적용하였다. 유용한 지식 습득이었다.)

 

 

class Solution {

    private static StringBuilder name2;
    private static StringBuilder AAAAA = new StringBuilder(); //다 탐색했나 비교용 다 A가 되었으면 끝난거임
    private static int answer = 0;

    public int solution(String name) {
        name2 = new StringBuilder(name);
        for (int i = 0; i < name.length(); i++) {
            AAAAA.append('A');
        }
        int totalMoveCount = name.length() - 1;
        int start = 0;

        //많이 움직여도 문자열 길이 -1 만큼이므로 그만큼 반복
        while (totalMoveCount > 0) {
            // 완료시 break (해결된 인덱스는 A로 바꿔주는데 A는 안움직여도 되는 인덱스를 의미하게했다.)
            if (AAAAA.toString().equals(name2.toString())) {
                break;
            }
            // 첫번쨰 인덱스만 따로 처리
            if (totalMoveCount == name.length() - 1 && name2.toString().charAt(0) != 'A') {
                answer += moveUpDown(name2.charAt(0));
                name2.setCharAt(0, 'A');
            }
            // 왼쪽 오른쪽으로 어디로 이동할지 결정
            Index index = checkIndex(start);
            // 좌우 이동 카운트 +
            answer += index.moveCount;
            // 해당 인덱스 상하 이동 계산해서 카운트 +
            answer += moveUpDown(name2.charAt(index.currentIndex));
            // 현재 인덱스 세팅
            start = index.currentIndex;
            // 해결한 인덱스는 A로 바꿔줌
            name2.setCharAt(index.currentIndex, 'A');
            totalMoveCount--;
        }
        System.out.println(answer);
        return answer;
    }

    //'A' 가 아닌 인덱스 도착하는데 왼쪽으로 가는거와 오른쪽으로 가는것 중 최소인거의 인덱스와 총 이동거리 반환
    public static Index checkIndex(int start) {
        int tmpStart = start;
        int rightMoveCount = 0;
        int rightIndex = 0;
        int leftMoveCount = 0;
        int leftIndex = 0;
        //오른쪽으로 이동한 경우
        for (int i = 0; i < name2.length(); i++) {
            start++;
            rightMoveCount++;
            if (start > name2.length() - 1) {
                start = 0;
            }
            if (name2.charAt(start) != 'A') {
                rightIndex = start;
                break;
            }
        }
        //왼쪽으로 이동한 경우
        start = tmpStart;
        for (int i = 0; i < name2.length(); i++) {
            start--;
            leftMoveCount++;
            if (start < 0) {
                start = name2.length() - 1;
            }
            if (name2.charAt(start) != 'A') {
                leftIndex = start;
                break;
            }
        }
        // 왼쪽 오른쪽 이동 중 최소를 반환
        if (rightMoveCount <= leftMoveCount) {
            return new Index(rightMoveCount, rightIndex);
        } else {
            return new Index(leftMoveCount, leftIndex);
        }
    }

    // 위아래로 움직이는 최솟값 반환
    private static int moveUpDown(char dest) {
        int distance = Math.abs('A' - dest);
        int zDistance = Math.abs('Z' - dest) + 1;
        int minDistance = Math.min(distance, zDistance);
        return minDistance;
    }

    static class Index {
        int moveCount; // 조이스틱 움직인 횟수
        int currentIndex; // 현재 인덱스

        Index(int moveCount, int currentIndex) {
            this.moveCount = moveCount;
            this.currentIndex = currentIndex;
        }
    }
}

 

 

댓글과 공감은 큰 힘이됩니다. 감사합니다!