백준 4949번 : 균형잡힌 세상
이번 문제는 직전에 풀었던 (기록은 하지 않았다.) 괄호 문제와 비슷하다.
다만, 괄호의 종류가 늘어났고, 문제에서 “사이에 있는 문자열도 균형”이라는 말이 무슨 말인지 헷갈릴 수 있다.
사실은 그냥 괄호 문제.ver2 이다.
직전에 풀었던 괄호 문제의 소스코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Stack<Character> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
while (n-- > 0) {
String str = br.readLine();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(') {
stack.push(ch);
} else if (!stack.isEmpty() && ch == ')') {
stack.pop();
} else {
stack.push(ch);
break;
}
}
if (stack.isEmpty())
sb.append("YES").append('\n');
else
sb.append("NO").append('\n');
stack.clear();
}
System.out.println(sb);
}
}
크게 설명할 부분은 스택을 사용하여 괄호의 짝을 찾아주는 방식이다.
문자열을 입력 받고 ‘(‘ 여는 괄호가 입력되면 stack에 저장하고 스택이 비어있지 않은데 닫는 괄호가 있다면 짝을 찾았다는 의미이므로 여는 괄호를 스택에서 빼준다.
만약 스택이 비어있는데 ‘)’ 닫는 괄호가 입력되면 이미 밸런스는 무너진 것이므로 스택에 해당 닫는 괄호를 넣고 즉시 반복문을 종료 시킨 다음 결과적으로 no를 출력시키게 된다.
스택은 주로 이런 밸런스 문제가 많이 출제되는 것 같다.
이 알고리즘을 활용하면 이번 문제인 “균형잡힌 세상”도 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(' || ch == '[') {
stack.push(ch);
} else if (ch == ')') {
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else {
isBalanced = false;
break;
}
} else if (ch == ']') {
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
isBalanced = false;
break;
}
}
}
우선은 내부 조건식부터 변형이 필요하다.
문제에서는 ‘()’와 ‘[]’의 균형을 맞춰야 한다고 되어있기 때문에 괄호 문제에서 종류가 늘어난 만큼 조건을 분기한 것이다.
입력된 여는 괄호의 종류가 두 개이기 때문에 ‘(‘와 ‘[‘로 분기했다.
그 다음으로는 각각 상황에 맞게 닫는 괄호, 짝을 찾아준다.
다만 종류가 늘어났기 때문에 바로 pop하면 안되고 요소를 빼버리지 않고 찾아주기만 하는 peek 함수를 사용하여 가장 위에 있는 여는 괄호가 현재 입력된 닫는 괄호와 짝이 맞는지를 분기했다.
여기서 “만약 ‘([)]’ 이런식으로 입력된다면?” 이라고 할 수 있는데, 이는 앞서 말한 헷갈릴 수도 있는 “사이에 있는 문자열도 균형” 이 조건에 위배된다.
즉, 여는 괄호와 닫는 괄호는 짝에 맞게 먼저 입력된다는 의미이다.
그렇기 때문에 각 종류 별로 짝을 순서대로 찾아주기만 하면 된다.
또 주의 해야할 점이 한 가지 더 있다.
만약 “ .”과 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있어야한다는 조건이다.
이를 해결하기 위해 플래그 변수를 사용했다.
플래그 변수는 간단히 스위치 정도로 생각하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while ((str = br.readLine()) != null) {
if (str.equals("."))
break;
boolean isBalanced = true;
/*
...
괄호 탐색
...
*/
if (!stack.isEmpty() || !isBalanced)
sb.append("no").append('\n');
else
sb.append("yes").append('\n');
stack.clear();
}
지금 실행 중인 while 만에 선언한 isBalanced 가 플래그 변수이다.
이는 기본적으로 모든 입력된 문자열을 균형잡힌 문자열로 가정하고 진행하되 이전 괄호 탐색 알고리즘에서 봤듯이 괄호의 짝이 없다면 false로 초기화하고 반복문을 종료 시킨다.
이후 StringBuilder로 출력 값을 구성할 때의 조건으로 isBalanced가 true인지, false인지 파악해주면 된다.
전체적인 흐름을 보면 이전 괄호 문제와 같지만 추가적인 로직이 있어 헷갈릴 수 있다.
전체 소스 코드는 아래와 같다.
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
46
47
48
49
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Character> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
String str;
while ((str = br.readLine()) != null) {
if (str.equals("."))
break;
boolean isBalanced = true;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(' || ch == '[') {
stack.push(ch);
} else if (ch == ')') {
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else {
isBalanced = false;
break;
}
} else if (ch == ']') {
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
isBalanced = false;
break;
}
}
}
if (!stack.isEmpty() || !isBalanced)
sb.append("no").append('\n');
else
sb.append("yes").append('\n');
stack.clear();
}
System.out.println(sb);
}
}
이 문제는 예전에 한 번 풀어봤던 문제이다.
그렇다고 해서 보자마자 기억나진 않았다.
다행히 직전에 괄호 문제를 하나 풀고와서 분기를 나눌 수 있었다.
하지만 괄호 안의 문자열도 균형이 잡혀야된다는게 무슨 의미인지 좀 오래 헤맸다.
이 문제를 풀기 전에 스택 문제를 4문제를 더 풀었는데, 해당 문제들은 스택의 기본적인 사용법 정도를 묻는 문제였기 때문에 따로 작성하진 않았다.
앞으로도 이런 식으로 꼭 기억해야할, 혹은 핵심적인 문제만 기록할 생각이다.
(블로그가 무거워질 수 있기 때문에 이전처럼 무분별하게 전부 기록하지 않을 것이다.)