[백준/JAVA] 16719번: ZOAC

📖 문제

16719번: ZOAC

 

 

💡  풀이 방식

• 재귀

재귀 메소드 zoac에서 (처음 시작 부분, 끝나는 부분)을 인자로 받는다.

그리고 시작하는 부분과 끝나는 부분 사이에 있는 글자들 중에서 사전식 정렬했을 때 가장 앞에 오는 글자를 방문처리한다.

그리고 방문한 적 있는 idx들을 출력한다. 

아까 발견한 idx에서 +1한 위치와 끝나는 문자열 위치를 넘기며 메소드를 호출한다. (재귀)

이어서 시작하는 문자열 위치와 idx에서 -1한 위치를 넘기며 메소드를 호출한다.

 

 

💥 유의사항

재귀 메소드 호출할 때 아래 순서를 반드시 맞춰주어야 사전식 순서가 맞는다.

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

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static String str;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        str = br.readLine();
        visited = new boolean[str.length()];
        
        zoac(0, str.length() - 1);  // 처음 시작할 부분, 끝내는 부분
        System.out.println(sb);
    }
    
    private static void zoac(int left, int right) {  // 처음 시작할 부분, 끝내는 부분
        if(left > right)    return;
        
        // 현재 문자열 中 사전식 순서가 가장 낮은 글자 찾기
        int idx = left;
        for(int i = left ; i <= right ; i++) {
            if(str.charAt(idx) > str.charAt(i)) {
                idx = i;
            }
        }
        visited[idx] = true;
        
        for(int i = 0 ; i < str.length() ; i++) {
            if(visited[i]) {
                sb.append(str.charAt(i));
            }
        }
        sb.append("\n");
        
        // 사전식 순서 맞추기 (반드시 재귀 이 순서로!)
        zoac(idx + 1, right); // 현재 문자보다 뒤에 있는 문자열 탐색
        zoac(left, idx - 1); // 현재 문자보다 앞에 있는 문자열 탐색
    }
}
 

 

---

💦 어려웠던 점

- 뒷문자열 탐색하고 다시 앞 문자열을 어떻게 탐색하지 했는데 재귀를 사용하면 되는 것이었다.

- 재귀 문제인 걸 알면서도 방문 배열 활용할 생각을 하지 못 했다.ㅠ

- 어떤 변수를 갖고 재귀를 돌려야 할까 > 탐색 문자열의 시작할 부분, 끝낼 부분

 

 

1회독	2회독	3회독	4회독	5회독
V	12.23

---

(참고)

✔ 풀이 참고

백준 16719 ZOAC(JAVA)

[ BOJ ][JAVA][16719] ZOAC