백준 16719 ZOAC(JAVA)

문제

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

16719번: ZOAC

코드

package com.company;

import java.io.*;

public class Main {
    private static BufferedReader br;
    private static StringBuilder sb = new StringBuilder();
    static String input;
    static boolean[] visited;

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

        input = br.readLine();
        visited = new boolean[input.length()];

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

        br.close();
        System.out.println(sb.toString());
    }

    private static void zoac(int left, int right) throws IOException {
        if (left > right) return;

        int idx = left;

        // left와 right 사이에 있는 글자중 사전식 순서가 가장 낮은 글자를 찾는다.(idx)
        for (int i = left; i <= right; i++) {
            if (input.charAt(idx) > input.charAt(i)) {
                idx = i;
            }
        }
        visited[idx] = true;

        for (int i = 0; i < input.length(); i++) {
            if (visited[i]) {
                sb.append(input.charAt(i));
            }
        }
        sb.append("\\n");

        // 여기도 순서가 안맞으면 틀렸습니다를 확인할 수 있다.
        // 반드시 이 dfs 순서로 재귀를 구현해야 한다.
        // 그래야 사전식 순서가 맞춰진다.
        zoac(idx + 1, right);
        zoac(left, idx  - 1);
    }
}

풀이

문제 풀이에 대한 감은 잡았지만 생각보다 오래 고민한 문제이다. 재귀로 풀어야할것 같은 느낌은 받았지만 구현에 있어서 제대로 수행하지 못해 다른 분의 코드를 참고하였다. 우선 zoac메서드에서 처음 시작하는 부분과 끝내는 부분을 인자로 받는다. 그리고 시작 하는 부분과 끝내는 부분사이에서 사전식으로 했을때 순서가 가장 낮은 글자의 visit를 방문 처리해준다. 그리고 visit가 true인, 즉 이미 방문했는 idx를 출력해준다. 그리고 아까 발견했는 idx에서 +1한 위치와 인자로 받았는 끝내는 문자열의 위치를 넘기면서 메서드를 호출해준다. 그리고 다음으로는 인자로 받았는 시작하는 문자열의 위치와 idx - 1한 위치를 넘겨준다.