💡 문제
![](https://velog.velcdn.com/images/longbright_choi/post/452ca95c-cd4c-4bdf-997f-d7819708ebe0/image.png)
![](https://velog.velcdn.com/images/longbright_choi/post/c5d947ba-ab6a-4f6c-a54e-febd07b378ba/image.png)
💬 입출력 예시
![](https://velog.velcdn.com/images/longbright_choi/post/edc95633-1fd7-4b7c-9870-03bf7232317e/image.png)
📌 풀이(소스코드)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeSet;
public class Main {
static ArrayList<Pos> posList = new ArrayList<>();
static TreeSet<String> set = new TreeSet<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
posList.add(new Pos(stack.pop(), i));
}
}
dfs(0, posList.size(), input);
set.remove(input);
StringBuilder sb = new StringBuilder();
for (String s : set) {
sb.append(s).append("\n");
}
System.out.println(sb);
}
private static void dfs(int depth, int n, String s) {
if (depth == n) {
set.add(s.replaceAll(" ", ""));
return;
}
Pos pos = posList.get(depth);
StringBuilder sb = new StringBuilder(s);
sb.setCharAt(pos.start, ' ');
sb.setCharAt(pos.end, ' ');
dfs(depth + 1, n, sb.toString());
dfs(depth + 1, n, s);
}
static class Pos {
int start;
int end;
public Pos(int start, int end) {
this.start = start;
this.end = end;
}
}
}
📄 해설
접근
- 스택, DFS,
TreeSet
을 사용해야 해결할 수 있는 문제이다.
- 이 문제 또한 접근이 상당히 어려웠고,
TreeSet
을 사용한 적이 없어서 결국 다른 사람의 풀이를 보고 풀었다.
- 또한 괄호의 시작과 끝의 위치를 나타낼 클래스
Pos
를 구현해야한다.
- 해당 괄호를 제거하는 경우와 그렇지 않은 경우를 위해 DFS 알고리즘을 사용해야한다.
- 사전 순으로 출력해야한다는 조건을 맞추기 위해 자동으로 정렬되는
TreeSet
을 사용한다.
과정
- 정수형 스택 하나와
TreeSet
객체 하나, Pos
리스트를 사용한다.
- 입력 문자열에서 여는 괄호를 만난 경우는 스택에 현재 인덱스의 번호를 넣고, 닫는 괄호를 만난 경우 스택에서 괄호의 시작 위치를 꺼내어
Pos
객체를 새로 생성하고, 리스트에 추가한다.
- DFS 알고리즘을 수행해서 결과 문자열들을 담을
TreeSet
을 만든다.
depth
가 괄호의 개수인 n
과 같은 경우, 공백을 제거하고 TreeSet
에 추가한다.
- 그렇지 않은 경우는
depth
인덱스에 위치한 괄호의 위치 정보를 꺼내서 해당 괄호를 제거한 문자열을 하나 만들고, 괄호를 제거하는 경우와 그렇지 않은 경우로 재귀 호출을 진행한다.
- DFS 알고리즘 수행이 끝난 후,
TreeSet
에서 입력 받았던 문자열을 제거한 다음, TreeSet
에 존재하는 모든 문자열을 출력한다.