[Java] 백준(실버-4) 4949번 - 균형잡힌 세상
문제 풀이
이번 문제는 괄호 문자열에서 괄호 종류가 “(“와 “[“로 두가지이다.
단일 괄호 문자열과 비교하면 서로 다른 괄호의 짝이 맞는지를 검증해야한다.
아이디어 도출
- ”(“는 “)”를 value값으로, “[“는 “]”를 value값으로 가지는 Map을 미리 만들어둔다.
- 개행 기준으로 주어지는 문자열에서 “(“나 “[“가 나온다면 스택에 삽입한다.
- ”)”가 나온다면 현재 닫혀야할 괄호가 “)”가 맞는지, “]”가 나온다면 현재 닫혀야할 괄호가 “]”가 맞는지 최신 열린 괄호(스택의 맨 위 값)를 key값으로 Map에서 value값을 조회하여 확인한다.
- 괄호 짝 검증후 스택이 비어있다면 짝이 맞으므로 yes를 출력한다.
- 주어진 문자열에서 괄호가 없더라도 yes를 출력한다.
- 위 괄호 짝 검증 과정 중 괄호 짝이 맞지 않는다면 NO를 출력한다.
- EmptyStackException 예외가 발생할 경우 no를 출력한다.
- 열린 괄호와 닫혀야 할 괄호 짝이 하나라도 맞지 않는다면 no를 출력한다.
- 입력 문자열이 “.”으로만 이루어져 있다면 입력의 끝으로 간주하고 입력을 종료한다.
아이디어가 복잡해 보일 수 있는데, 핵심은 “(“ 및 “[” 열린 괄호들이 잘 닫혀있는지 확인하는 것이다.
말로 설명하자니 길어지는 것 같아 바로 코드를 작성해보자.
1
2
3
HashMap<Character, Character> bracket_map = new HashMap<>();
bracket_map.put('(', ')');
bracket_map.put('[', ']');
먼저 여는 괄호 “(“와 “[“의 짝을 미리 Map에 저장해둔다.
1
2
3
4
5
6
7
while(true) {
String input = br.readLine();
Stack<Character> bracket_list = new Stack<>();
boolean brackets = true;
if(input == "." || input.length() == 1) break;
...
}
주어진 문자열을 담을 input String과 여는 괄호들을 담아둘 Stack인 bracket_list, 짝이 안맞을 경우에 상태를 변경할 boolean 변수 brackets를 선언하자.
“.” 마침표 하나가 입력문자열로 들어올 때까지 입력을 받아야 하기에 while문 내에서 탈출조건을 작성했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while(true) {
...
try {
for(int i=0; i<input.length(); i++) {
if(input.charAt(i) == '(') bracket_list.push('(');
else if(input.charAt(i) == '[') bracket_list.push('[');
if(input.charAt(i) == ')') {
if(bracket_map.get(bracket_list.peek()) == ')') bracket_list.pop();
else brackets = false;
}
else if(input.charAt(i) == ']') {
if(bracket_map.get(bracket_list.peek()) == ']') bracket_list.pop();
else brackets = false;
}
}
if(bracket_list.empty() && brackets == true) bw.write("yes"+"\n");
else bw.write("no"+"\n");
} catch(EmptyStackException e) {
bw.write("no"+"\n");
}
}
- EmptyStackException 예와 처리를 하기위해서 try/catch문 내에서 여는 괄호 “(“, “[“가 올 때마다 스택에 삽입해둔다.
- 주어진 문자열에서 닫는 괄호 “)”가 나왔다면 현재 스택에 담긴 최신 값(맨 위)을 키로 Map의 value값을 조회하여 닫혀야 할 괗로가 “(“인지 확인하며, “]”도 동일하게 수행한다.
위 과정을 수행하며 brackets가 false이거나 스택이 비어있지 않다면 괄호 짝이 맞지 않는 것이기에 no를 출력한다.
물론 EmptyStackException 예외가 발생해도 짝이 맞지 않는 것이기에 no를 출력한다.
스택이 비어있고, brackets이 true라면 정상적으로 괄호들의 짝이 맞는 것이기 때문에 yes를 출력하면 된다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
HashMap<Character, Character> bracket_map = new HashMap<>();
bracket_map.put('(', ')');
bracket_map.put('[', ']');
while(true) {
String input = br.readLine();
Stack<Character> bracket_list = new Stack<>();
boolean brackets = true;
if(input == "." || input.length() == 1) break;
try {
for(int i=0; i<input.length(); i++) {
if(input.charAt(i) == '(') bracket_list.push('(');
else if(input.charAt(i) == '[') bracket_list.push('[');
if(input.charAt(i) == ')') {
if(bracket_map.get(bracket_list.peek()) == ')') bracket_list.pop();
else brackets = false;
}
else if(input.charAt(i) == ']') {
if(bracket_map.get(bracket_list.peek()) == ']') bracket_list.pop();
else brackets = false;
}
}
if(bracket_list.empty() && brackets == true) bw.write("yes"+"\n");
else bw.write("no"+"\n");
} catch(EmptyStackException e) {
bw.write("no"+"\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
회고
- 단일 괄호 문자열에서 괄호의 짝을 스택만으로 구현이 가능했지만, 다중 괄호 문자열에서는 별도로 여는 괄호들의 짝이 맞는지를 알아야 하기에 괄호들의 짝을 별도로 담아둘 HashMap을 함께 활용하여 문제를 풀 수 있었다.
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.