백준 9081 자바 - 단어 맞추기 (BOJ 9081 JAVA)

문제 : boj9081

 

  이하 설명은 이해의 편의를 위해 숫자로 설명해보겠다. 실제로 이 문제를 풀때도 문자를 아스키코드를 기준으로 변경해서('A'~'Z'까지 나오므로 각각을 숫자 0~25로 대입) 풀어야 한다. 내 풀이는 그리디 이다.

 

 

1.

  문자를 뒤에서부터 보면서, 같거나 증가하는 경우는 계속 진행하고 처음으로 더 작아진 경우를 찾는다. (문자로 따지면 ADCB라면 D->A일 때 작아진다.)

이하 그림에서는 9->3이 처음으로 작아진 부분이다. 처음으로 숫자가 감소하는 부분에 나왔던 '3'에 해당하는 위치를 T라고 적겠다.

2. 

  T위치와, 그 이후에 나온 숫자를 몇 번씩 나왔는지 카운팅한다. 이하 그림에서 idx 부분이 실제 숫자에 대입된다(문자라면 'A'~'Z'까지 카운팅하면 된다.) 예를들어 idx=9일 때 cnt=2인데, T를 포함한 그 이후의 위치에서 '9'가 2번 나왔다는 의미이다.

 

3.

  T미만의 위치(279134)에 있는 수는 그대로 출력하면 된다. 그리고 T에 해당하는 숫자(3)를 초과하는 수 중 (즉, 4 이상 중) 가장 먼저 나온 숫자를 T 위치에 넣는다. 그리고 해당 숫자의 cnt를 1 감소시킨다.

 

4.

  이후 카운팅해둔 배열을 idx 0부터 차례대로 보면서, 해당 숫자가 나온 횟수만큼 뒤에 붙이면 된다.

 

위 과정을 문자 'A'~'Z'를 0~26으로 보고 똑같이 진행하면 된다. 예외사항으로 한번도 작아진 경우가 없다면 그대로 출력하면 된다. (e.g. 'ZOO')

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();
        while(t-->0) {
            String s = br.readLine();
            int[] cnt = new int['z'-'a'+1];
            char bf = s.charAt(s.length()-1);
            cnt[s.charAt(s.length()-1)-'A']++;
            int i = s.length()-2;
            int downIdxCharAscii = 0;
            for (; i >= 0; i--) {
                char cur = s.charAt(i);
                cnt[cur-'A']++;
                if (cur < bf) {
                    downIdxCharAscii = cur-'A';
                    break;
                }
                bf = cur;
            }

            if (i < 0) {
                answer.append(s).append('\n');
                continue;
            }

            for (int j = 0; j < i; j++)
                answer.append(s.charAt(j));

            for (int j = downIdxCharAscii+1; j < cnt.length; j++) {
                if (cnt[j] > 0) {
                    cnt[j]--;
                    answer.append((char)('A'+j));
                    break;
                }
            }

            for (int j = 0; j < cnt.length; j++) {
                for (int k = 0; k < cnt[j]; k++) {
                    answer.append((char)('A'+j));
                }
            }
            answer.append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}