백준 3663번: 고득점 (Java)

https://www.acmicpc.net/problem/3663

3663번: 고득점

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

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

 

 

 

 

 

 

 

---

 

풀이

0) 글자 바꾸는건 별로 안 어렵습니다: x를 'A'와의 거리'라고 정의하면, 한 글자를 바꾸는 건 min(26-x, x)번 버튼을 누르면 됩니다.

1) 오른쪽 갔다가 왼쪽 갔다가...하는 경우의 수를 따져보다보면 감이 잘 안 잡힙니다. 저처럼 멘붕상태에 빠지지 말고, 차분히 경우를 나눌 필요가 있습니다. 오른쪽으로 쭉 가는 (가장 평범한) 케이스가 최소인 경우가 있으며('AAAAAABBBB'), 왼쪽으로 쭉 가는 케이스가 최소인 경우도 있습니다('ABAAAAA'). 그리고 더 나아가, 오른쪽으로 갔다가 꺾어서 왼쪽으로 쭉 가는 케이스가 최소인 경우도 있고('ABAAAAAAABB'), 왼쪽으로 갔다가 오른쪽으로 꺾어서 쭉 가는 케이스가 최소일 수도 있습니다('ABBBBAAAAAAAAAB').

2) 여기서 한 번 더 꺾는 경우(즉, 2번 이상 꺾는 경우)는 무조건 최소가 될 수 없다는 아이디어를 얻어야 합니다. 예를 들어, 0에서 오른쪽으로 x만큼 갔다가 왼쪽으로 꺾어 y만큼 가고, 다시 꺾어 z만큼 갔다라고 가정을 합시다. 여기서 'x<z<y'가 아닌 경우는 사실 자명하게(머리속에서 생각해서 자명하다고 느끼는 거니, 혹시 자명하지 않게 느껴진다면 그려보시길...!) 최소 움직임이 아닐 테니 제외를 하고, 'x<z<y'인 경우는 사실 처음부터 왼쪽으로 y만큼 갔다가 오른쪽으로 꺾어 z까지 가는 것이 더 적은 움직임입니다. 

3) 그러면 3가지 경우만 따지면 되는데, i에 대해 for문을 돌면서, i보다 크면서 가장 먼저 A가 아닌 원소가 나오는 칸을 기록해둡니다('idx'라 합시다.). 그러면,

(오른쪽으로 갔다가 왼쪽으로 가는 경우) = (2*I + (문자열의 길이 - idx))

(왼쪽으로 갔다가 오른쪽으로 가는 경우) = (2*(문자열의 길이 - idx) + i)

가 됩니다. 코드 구현상에서 idx==(문자열의 길이)인 경우 왼쪽으로 쭉 가는 경우, i == 0인 경우 오른쪽으로 쭉 가는 경우도 체크를 하게 됩니다.

 

배운 점

'아이디어가 생각 안 난 그리디 문제'만큼 어려운 문제가 있을까 싶습니다. 새로운 아이디어를 배웠습니다. 또한 구현도 되게 치밀하고 살짝 헷갈리기에, 잘 봐둘 필요가 있습니다.

그나저나 프로그래머스에선 이 문제가 lv.2로 분류되어 있던데, 진짜...? 🤔

 

 

코드

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String str = br.readLine();
            int N = str.length();
            int ans = 0;
            int move = N-1; // 왼쪽으로 쭉 가는 경우
            for (int i = 0; i < N; i++) {
                if (str.charAt(i) > 'A') {
                    int x = str.charAt(i) - 'A';
                    ans += Math.min(26-x, x);
                }
                
                int idx = i+1;
                while (idx < N && str.charAt(idx) == 'A') {
                    idx++;
                }
                // 왼쪽으로 갔다가 오른쪽을 가는 경우
                // 오른쪽으로만 쭉 가는 경우도 포함하고 있음(idx==N인 경우)
                move = Math.min(move, 2*(N-idx) + i); 
                // 오른쪽으로 갔다가 왼쪽으로 가는 경우    
                // 왼쪽으로만 쭉 가는 경우도 포함하고 있음(i == 0인 경우)
                move = Math.min(move, 2*i + (N-idx));
            }
            System.out.println(ans + move);
        }
    }
 
}