[백준] 16719번 : ZOAC - 자바[Java]

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

16719번: ZOAC

 

풀이

문자열의 길이는 최대 100자이므로 n <= 100이다. 따라서 시간복잡도가 O(N^2)인 풀이를 사용해도 괜찮다고 생각했다.

 

먼저 입력으로 주어지는 문자열에서 각 문자와 그 위치를 저장하는 자료구조가 필요하다고 생각했다.

그래서 Data 클래스를 생성하고, 이후 정렬을 사용하기 위해 implements Comparable 구현하였다.

    static class Data implements Comparable<Data> {
        char ch;
        int idx;
        public Data(char ch, int idx) {
            this.ch = ch;
            this.idx = idx;
        }

        @Override
        public int compareTo(Data o) {
            if (this.ch == o.ch) {
                return this.idx - o.idx;
            }
            return this.ch - o.ch;
        }
    }

 

메인 함수에서는 ArrayList<Data> list를 생성 후 Data를 추가하였다. 그다음에 list를 정렬하고 func(str, list)를 호출하여 정답을 출력하도록 하였다.

    static StringBuilder sb = new StringBuilder();

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

        String str = br.readLine();
        ArrayList<Data> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            Data data = new Data(str.charAt(i), i);
            list.add(data);
        }

        Collections.sort(list); // 정렬
        func(str, list);

        bw.write(sb.toString());
        bw.flush();

        br.close();
        bw.close();
    }

 

void func(String str, ArrayList<Data> list)

str과 정렬된 상태인 list를 사용하여 정답을 출력하도록 한다.

    private static void func(String str, ArrayList<Data> list) {
        boolean[] check = new boolean[str.length()];
        int startIdx = -1;

        while (!isCompleted(check)) { // 모든 문자가 check되었으면 종료
            // 리스트 전체 탐색하여 문자 출력
            for (Data data: list) {
                if (!check[data.idx] && data.idx > startIdx) {
                    startIdx = data.idx;
                    check[data.idx] = true;
                    print(check, str);
                }
            }

            // update startIdx
            // 마지막 위치부터 앞으로 가면서 문자가 체크되어있는지 연속적으로 확인한 후, 체크하지 않은 문자가 있을 시 break
            int i = list.size() - 1;
            for (; i >= 0; i--) {
                if (!check[i]) break;
            }

            // 체크하지 않은 문자가 있는 구간이 있을 때 그 문자에 앞에 있는 문자 중 가장 가까운 체크된 문자의 위치를 startIdx로 지정
            boolean flag = false;
            for (;i >= 0; i--) {
                if (check[i]) {
                    flag = true;
                    startIdx = i;
                    break;
                }
            }
            if (!flag) startIdx = -1; // 앞에 체크된 문자가 없으면 startIdx를 -1로 초기화
        }
    }

    private static boolean isCompleted(boolean[] check) {
        for (int i = 0; i < check.length; i++) {
            if (!check[i]) {
                return false;
            }
        }
        return true;
    }

    private static void print(boolean[] check, String str) {
        for (int i = 0; i < str.length(); i++) {
            if (check[i]) {
                sb.append(str.charAt(i));
            }
        }
        sb.append("\n");
    }

모든 문자가 쓰였는지 확인하기 위해 boolean[] check 배열을 사용하였고, startIdx를 사용하여 해당 문자가 현재 출력해야할 순서인지 판별한다.

 

모든 문자가 체크되기까지 다음을 반복한다.

1. 리스트의 모든 원소를 탐색하여 문자를 출력한다.

    1-1. 현재 문자가 아직 체크되지 않았고, startIdx보다 위치가 나중에 있다면 startIdx를 업데이트하고 현재 문자 위치를 check 한다.

2. startIdx를 업데이트한다.

    2-1. 마지막 위치부터 앞으로 가면서 문자가 체크되어있는지 연속적으로 확인한 후, 체크하지 않은 문자가 있을 시 break

    2-2. 체크하지 않은 문자가 있는 위치에서, 그 앞에 있으며 체크된 문자들 중 가장 가까운 위치를 startIdx로 지정

    2-3. 앞에 체크된 문자가 없으면 startIdx를 -1로 초기화

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    static class Data implements Comparable<Data> {
        char ch;
        int idx;
        public Data(char ch, int idx) {
            this.ch = ch;
            this.idx = idx;
        }

        @Override
        public int compareTo(Data o) {
            if (this.ch == o.ch) {
                return this.idx - o.idx;
            }
            return this.ch - o.ch;
        }
    }

    static StringBuilder sb = new StringBuilder();

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

        String str = br.readLine();
        ArrayList<Data> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            Data data = new Data(str.charAt(i), i);
            list.add(data);
        }

        Collections.sort(list); // 정렬
        func(str, list);

        bw.write(sb.toString());
        bw.flush();

        br.close();
        bw.close();
    }

    private static void func(String str, ArrayList<Data> list) {
        boolean[] check = new boolean[str.length()];
        int startIdx = -1;

        while (!isCompleted(check)) { // 모든 문자가 check되었으면 종료
            // 리스트 전체 탐색하여 문자 출력
            for (Data data: list) {
                if (!check[data.idx] && data.idx > startIdx) {
                    startIdx = data.idx;
                    check[data.idx] = true;
                    print(check, str);
                }
            }

            // update startIdx
            // 마지막 위치부터 앞으로 가면서 문자가 체크되어있는지 연속적으로 확인한 후, 체크하지 않은 문자가 있을 시 break
            int i = list.size() - 1;
            for (; i >= 0; i--) {
                if (!check[i]) break;
            }

            // 체크하지 않은 문자가 있는 구간이 있을 때 그 문자에 앞에 있는 문자 중 가장 가까운 체크된 문자의 위치를 startIdx로 지정
            boolean flag = false;
            for (;i >= 0; i--) {
                if (check[i]) {
                    flag = true;
                    startIdx = i;
                    break;
                }
            }
            if (!flag) startIdx = -1; // 앞에 체크된 문자가 없으면 startIdx를 -1로 초기화
        }
    }

    private static boolean isCompleted(boolean[] check) {
        for (int i = 0; i < check.length; i++) {
            if (!check[i]) {
                return false;
            }
        }
        return true;
    }

    private static void print(boolean[] check, String str) {
        for (int i = 0; i < str.length(); i++) {
            if (check[i]) {
                sb.append(str.charAt(i));
            }
        }
        sb.append("\n");
    }
}

 

다른 풀이 - 재귀

https://www.acmicpc.net/source/65093974

import java.util.Scanner;

public class Main {

    static String input;
    static boolean[] index = new boolean[100];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        input = sc.nextLine();
        foo(0,input.length()-1);
    }

    static void foo(int l,int r){
        char fastChar = '{';
        int idx = -1;

        for(int i=l;i<r+1;++i){
            if(!index[i] && fastChar>input.charAt(i)){
                fastChar = input.charAt(i);
                idx = i;
            }
        }

        if(idx==-1){
            return;
        }

        index[idx] = true;

        for(int i=0;i<=99;++i){
            if(index[i]==true){
                System.out.print(input.charAt(i));
            }
        }

        System.out.println();
        foo(idx+1,r);
        foo(l,idx-1);
    }

}

먼저 전체 구간에 대해서 가장 사전 순이 빠른 문자를 선택하고, 재귀를 사용하여 그 문자의 뒷부분, 앞부분을 차례로 탐색한다.