백준 16719 ZOAC (Java)

1. 문제

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.

바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

입력

첫 번째 줄에 알파벳 대문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다.

출력

규칙에 맞게 순서대로 문자열을 출력한다.

 

2. 풀이

이 문제의 조건을 성립시키기 위해서는 다음의 순서대로 출력해야 한다.

1. 가장 사전순으로 앞에 오는 문자를 출력한다.
2. 해당 문자 뒤에 따라오는 가장 사전순으로 앞에 오는 문자를 출력해야 한다.(사전순으로 빠른 순으로 출력하려면 가장 사전순으로 앞에 오는 문자를 최대한 앞에 가는 방법으로 문자를 추가해야 한다.)
3. 위의 규칙으로 모든 문자를 출력했다면 1번 문자 앞에 오는 가장 빠른 문자를 추가한다.

 문자를 선택해서 추가하고, 뒤 앞 순으로 같은 문자를 출력해야 하므로 분할 정복으로 문제를 풀 수 있다.

    private static void zoacPrint(int s, int e) {

        if (s > e) return;

        Character first = 'Z' + 1;
        int fidx = s;

        for (int i = s; i <= e; i++) {
            if (first > input.charAt(i)) {
                first = input.charAt(i);
                fidx = i;
            }
        }
        visit[fidx] = true;

        for (int i = 0; i < input.length(); i++) {
            if (visit[i]) {
                System.out.print(input.charAt(i));
            }
        }
        System.out.println();

        zoacPrint(fidx + 1, e);
        zoacPrint(s, fidx - 1);


    }

분할된 문자열의 처음부터 끝까지 가장 사전순으로 앞에 오는 문자를 추가한다. 이를 순서대로 출력한 뒤 해당 문자의 뒤, 앞에 대해 같은 로직을 수행한다. 모든 문자를 출력할 때 까지 반복하면 정답을 출력할 수 있다.

 

3. 코드 전문

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

public class Main {

    static String input;

    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        input = reader.readLine();
        visit = new boolean[input.length()];


        zoacPrint(0, input.length() - 1);

    }

    private static void zoacPrint(int s, int e) {

        if (s > e) return;

        Character first = 'Z' + 1;
        int fidx = s;

        for (int i = s; i <= e; i++) {
            if (first > input.charAt(i)) {
                first = input.charAt(i);
                fidx = i;
            }
        }
        visit[fidx] = true;

        for (int i = 0; i < input.length(); i++) {
            if (visit[i]) {
                System.out.print(input.charAt(i));
            }
        }
        System.out.println();

        zoacPrint(fidx + 1, e);
        zoacPrint(s, fidx - 1);


    }


}