CodingTest/알고리즘-풀이

백준 16719번 ZOAC 풀이 java

JeonSooMin 2025. 5. 22. 16:10

Relevace Framing 🧩

관련된 개념 : [[시뮬레이션]], [[재귀]]

1. 문제에 대하여 📦

(1) 조건 분석 📊

주어진 문장에서 아직 보여주지 않은 문자 중 하나를 추가했을 때, 사전 순으로 먼저 오는 단어들을 차례대로 출력한다.

만약 STARTLINK라는 단어가 주어지면

A
AI
AIK
AINK
ALINK
ARLINK
ARTLINK
SARTLINK
STARTLINK

이 순으로 와야 한다.

보면서 주목해야할 점은 다음과 같다.

  1. A 뒤쪽을 먼저 다 확인한 뒤, A의 앞쪽을 보고 있음.
  2. T 두 개 중 뒤쪽의 T가 먼저 나옴

그 이유는 다음과 같다. A가 알파벳 중 가장 사전 순이 빠른 문자인데, 이것의 앞에 어떤 문자가 나오는 것보다, 이것의 뒤에 문자를 두는 것이 항상 사전 순이 빠를 것이기 때문이다. 당현히 SA보다 AI가 더 빠를 것이다.
이는 A 뿐만 아니라 모든 문자에 적용된다. A이 다음이 A -> AI -> AIK -> AINK -> ALINK 인 것을 봐도, 하나의 문자가 선정되면, 그것의 오른쪽부터 먼저 다 확인 후 왼쪽으로 넘어간다. 그래서 T 또한 A의 오른쪽에 있는 것이 먼저 쓰인 후 왼쪽이 쓰이는 것이다.

2. 코드가 나오기까지 🛠️

KEY WORD: 재귀 , 시뮬레이션

위 문제의 분석을 그대로 구현한다.

  1. 문자열에서 확인해야할 범위를 특정하기 위해 맨 왼쪽 index와 맨 오른쪽 index를 인수로 받는다.
    (맨 처음 인수는 0, 문자열 길이 - 1 이다.)
  2. 현재 재귀에서 아직 방문안한 문자 중에 사전 순으로 가장 빠른 문자를 찾는다.
  3. 이후 해당 문자를 방문 표시한다.
  4. 방문 표시된 문자들을 앞에서부터 차례대로 출력한다.
  5. 이번 재귀 LEVEL에서 찾은 문자의 index +1부터 인수로 받은 오른쪽 index까지 한 번 더 재귀한다.
  6. 인수로 받은 왼쪽 index부터 이번 재귀 LEVEL에서 찾은 문자의 index -1 까지 한 번 더 재귀한다.

(1) 시간복잡도 분석 ⏳

문자열의 길이가 최대 100이라서 따로 생각 안해도 될 거 같다.

3. 코드 🌐

(1) SUDO CODE 💬

의사 코드는 위의 '코드가 나오기 까지' 부분 그대로니까 생략

(2) JAVA CODE ☕

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

public class Main {
    static String str;
    static boolean [] isVisited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        isVisited = new boolean[str.length()];
        zoac(0, str.length()-1);
    }

    public static void zoac(int left, int right) {
        // base-case
        if(left > right) return;

        int idx = left;
        for(int i = left; i <= right; i++){
            if(isVisited[i]) continue;
            if(str.charAt(i) < str.charAt(idx)) idx = i;
        }
        isVisited[idx] = true;

        for(int i = 0; i < str.length(); i++){
            if(isVisited[i]) System.out.print(str.charAt(i));
        }
        System.out.println();

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

    }
}

4. 트러블 슈팅 or 배운 점📝

  • 배열 하나로 문자열 하나 하나의 값과 문자열의 index를 동시에 표현하려고 했다. 이것이 구현을 더 어렵게 만들었다. 문자열은 문자열대로 두고, 그 문자열의 index만 배열로 표현하면 될 것이다.
  • 이 문제가 재귀 문제라는 것을 생각을 못했다. 아직 시뮬레이션 문제에 대한 역량이 부족함이 느껴지고 더 풀어봐야겠다.