[프로그래머스/42860] 조이스틱

18 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이(실패)
  • 두 번째 풀이(실패)
  • 세 번째 풀이 (성공)

☑️ 문제

프로그래머스 42860

☑️ 풀이

첫 번째 풀이(실패)

class Solution {
    public int solution(String name) {
        int answer = 0;
        String a = "A".repeat(name.length());
        int idx = 0;
        while (!name.equals(a)) {
            if (name.charAt(idx) != 'A') {
                answer += Math.min(name.charAt(idx) - 'A', 'Z' - name.charAt(idx) + 1); 
                name = name.substring(0, idx) + "A" + name.substring(idx + 1);
            } 
            
            if (name.charAt(idx) == 'A') {
                int idx1 = idx;
                int cnt1 = 0;
                int idx2 = idx;
                int cnt2 = 0;
                
                while (idx1 < name.length() - 1 && name.charAt(idx1) == 'A') {
                    idx1++;
                    cnt1++;
                }
                while (idx2 < name.length() - 1 && name.charAt(idx2) == 'A') {
                    if (idx2 == 0) {
                        idx2 = name.length() - 1;
                    } else {
                        idx2--;
                    }
                    cnt2++;
                }
                
                idx = cnt1 > cnt2 ? idx2 : idx1;
                answer += (cnt1 > cnt2) ? cnt2 : cnt1;
            }
        }
        
        return answer;
    }
}

• while 루프를 돌면서 A가 아닌 문자를 찾아 바꿔나갔다.
• 문자를 바꿀 때 Math.min(name.charAt(idx) - 'A', 'Z' - name.charAt(idx) + 1) 를 사용하여 최소 조작 횟수를 계산했다.
• 하지만, 현재 코드에서는 커서를 이동할 때 왼쪽/오른쪽 중 어디로 가야 하는지 최적으로 계산하지 못한다.
• 단순히 오른쪽(idx1)과 왼쪽(idx2) 인덱스를 비교하는 방식이므로 만약 A가 연속된다면 우회하는 것이 더 좋은 경우를 찾지 못한다.

두 번째 풀이(실패)

class Solution {
    public int solution(String name) {
        int answer = 0;
        StringBuilder sb = new StringBuilder("A".repeat(name.length()));
        int idx = 0;
        int move = name.length() - 1;
        
        while (!name.equals(sb.toString())) {
            if (name.charAt(idx) != 'A') {
                answer += Math.min(name.charAt(idx) - 'A', 'Z' - name.charAt(idx) + 1); 
                sb.setCharAt(idx, 'A');
            } 
            
            int next = idx + 1;
                
            // A가 아닌 자리 찾아내기
            while (next < name.length() && sb.charAt(next) == 'A') {
                next++;
            }
            
            // 앞쪽으로 돌아가기
            move = Math.min(move, (idx * 2) + name.length() - next);
            // 뒷쪽으로 돌아가기
            move = Math.min(move, (name.length() - next) * 2 + idx);
                
            idx = next;
        }

        answer += move;
        return answer;
    }
}

• StringBuilder를 이용해서 “AAA…”로 초기화하여 사용하도록 변경하였다.
• 또한, 커서를 이동하는 경우를 따져가며, 가장 적은 이동 거리를 갱신하였다.
• 실패 원인
  • while (!name.equals(sb.toString())) 로 문자열 비교 시 불필요한 문자열 변환이 반복되면서 실행 속도가 느려질 가능성이 높다.
  • 또한 idx를 next로 변경하는 방식이 모든 경우를 고려하지 않아 잘못된 이동 경로를 선택할 가능성이 있다.

세 번째 풀이 (성공)

class Solution {
    public int solution(String name) {
        int answer = 0;
        int move = name.length() - 1;
        
        for (int i = 0; i < name.length(); i++) {
            // A로 변경
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1); 
            
            // 커서 이동
            int next = i + 1;
                
            // 연속된 A 건너뛰기
            while (next < name.length() && name.charAt(next) == 'A') {
                next++;
            }
            
            // 앞쪽으로 돌아가기
            move = Math.min(move, (i * 2) + name.length() - next);
            // 뒷쪽으로 돌아가기
            move = Math.min(move, (name.length() - next) * 2 + i);            
        }

        answer += move;
        return answer;
    }
}

• 다른 사람의 풀이를 보고 참고하였다.
• for 루프를 이용해 문자열을 처음부터 끝까지 순회하도록 변경하였다.
• next 로 연속된 A를 건너뛰도록 한 후, move 값을 최적 이동 횟수로 갱신해준다.
  • 앞, 뒷쪽으로 이동하는 경우를 모두 계산하여 최솟값을 선택한다.