CodingTest/알고리즘-풀이
백준 16719번 ZOAC 풀이 java
JeonSooMin
2025. 5. 22. 16:10
Relevace Framing 🧩
관련된 개념
: [[시뮬레이션]], [[재귀]]
1. 문제에 대하여 📦
(1) 조건 분석 📊
주어진 문장에서 아직 보여주지 않은 문자 중 하나를 추가했을 때, 사전 순으로 먼저 오는 단어들을 차례대로 출력한다.
만약 STARTLINK
라는 단어가 주어지면
A
AI
AIK
AINK
ALINK
ARLINK
ARTLINK
SARTLINK
STARTLINK
이 순으로 와야 한다.
보면서 주목해야할 점은 다음과 같다.
- A 뒤쪽을 먼저 다 확인한 뒤, A의 앞쪽을 보고 있음.
- T 두 개 중 뒤쪽의 T가 먼저 나옴
그 이유는 다음과 같다. A가 알파벳 중 가장 사전 순이 빠른 문자인데, 이것의 앞에 어떤 문자가 나오는 것보다, 이것의 뒤에 문자를 두는 것이 항상 사전 순이 빠를 것이기 때문이다. 당현히 SA
보다 AI
가 더 빠를 것이다.
이는 A 뿐만 아니라 모든 문자에 적용된다. A이 다음이 A
-> AI
-> AIK
-> AINK
-> ALINK
인 것을 봐도, 하나의 문자가 선정되면, 그것의 오른쪽부터 먼저 다 확인 후 왼쪽으로 넘어간다. 그래서 T 또한 A의 오른쪽에 있는 것이 먼저 쓰인 후 왼쪽이 쓰이는 것이다.
2. 코드가 나오기까지 🛠️
KEY WORD
: 재귀
, 시뮬레이션
위 문제의 분석을 그대로 구현한다.
- 문자열에서 확인해야할 범위를 특정하기 위해 맨 왼쪽 index와 맨 오른쪽 index를 인수로 받는다.
(맨 처음 인수는 0, 문자열 길이 - 1 이다.) - 현재 재귀에서 아직 방문안한 문자 중에 사전 순으로 가장 빠른 문자를 찾는다.
- 이후 해당 문자를 방문 표시한다.
- 방문 표시된 문자들을 앞에서부터 차례대로 출력한다.
- 이번 재귀 LEVEL에서 찾은 문자의 index +1부터 인수로 받은 오른쪽 index까지 한 번 더 재귀한다.
- 인수로 받은 왼쪽 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만 배열로 표현하면 될 것이다.
- 이 문제가 재귀 문제라는 것을 생각을 못했다. 아직 시뮬레이션 문제에 대한 역량이 부족함이 느껴지고 더 풀어봐야겠다.