백준 16719 - ZOAC

Java

16719 번 - ZOAC

문제

접근 방법

문제 예시를 보면, 처음 문자열에서 가장 작은 문자를 찾아 출력하고 그 뒤의 문자열을 재탐색하여 가장 작은 문자를 찾는 방법으로 출력한다.
이후 처음 찾은 문자보다 앞에 있는 문자열을 다시 탐색하므로 분할 정복의 방식으로 재귀 함수로 나누어 해결하였다.

코드

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

public class Main {
	static int n, result, len;
	static char[] str;
	static boolean[] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	str = br.readLine().toCharArray();
    	len = str.length;
    	vis = new boolean[len];
    	zoac(0, len);

    	br.close();
	}

	private static void zoac(int s, int e) {
		int idx = -1, minN = 999;;
		// 현재 문자열에서 가장 작은 문자를 찾는다.
		for(int i = s; i < e; i++) {
			if(minN > str[i] && !vis[i]) {
				minN = str[i];
				idx = i;
			}
		}
		// 한번 찾았으면
		if(idx != -1) {
			// 해당 문자에 대한 방문 여부를 기록하고 출력
			vis[idx] = true;
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < len; i++) {
				if(vis[i])
					sb.append(str[i]);
			}
			System.out.println(sb.toString());
			// 이제 현재 문자보다 뒤에 있는 문자열을 탐색
			zoac(idx, e);
			// 이후 앞에 있는 문자열을 탐색
			zoac(s, idx);
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

뒷 문자열을 탐색하고 다시 앞의 문자열을 탐색하는 방법을 떠오르지 못해 해답을 참고한 문제.
한 가지만 생각하면 되는 거였지만, 그걸 생각하기가 어려웠다.

개선할 점