ZOAC

📍 문제 설명

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

16719번: ZOAC

 

💡 접근

처음에는 n개중에 1~n개 뽑는 조합으로 풀고 뽑힌 조합에서 걸러내려 했다.

근데 모든 경우를 뽑다보니 시간 초과가 났다.

이미 뽑은 문자들을 방문처리 하면서 출력하고 뽑는 문자들에 대해서 왼쪽 오른쪽 탐색을 해주면 불필요한 탐색을 안해도 된다.

 

👩‍💻 코드

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

public class Main {
    static char[] ch;
    static boolean[] visited;
    static StringBuilder sb;

    public void zoac(int left, int right) {
        if(left > right) return;
        int idx = left;

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

        zoac(idx + 1, right);
        zoac(left, idx  - 1);
    }

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

        String str = br.readLine();
        ch = str.toCharArray();
        visited = new boolean[ch.length];
        sb = new StringBuilder();
        t.zoac(0, ch.length-1);
        System.out.println(sb);
    }

}