📌 문제 : 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인
(와)만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된()문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열(x)도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어(())()와((()))는 VPS 이지만(()(,(())())), 그리고(()는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를YES와NO로 나타내어야 한다.
⬇️ 입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
⬆️ 출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면
YES, 아니면NO를 한 줄에 하나씩 차례대로 출력해야 한다.
💡 코드 : 괄호
✅ VPS가 되기 위해서는 여는 괄호
(와 닫는 괄호)가 짝이 맞아야 한다. 처음에는 이걸 스택으로 어떻게 해결해야 하나,, 싶었는데(를 스택에 저장하고,)가 나타나면 짝이 맞았으므로 스택에 저장된(를 하나 지워주는 방식으로 해결할 수 있었다.
문자열str의j번째 문자가(라면stack에(를 저장하고,)라면stack에 저장된(를 꺼내야 한다. 이 때,stack이 비어있지 않다면 저장된(를 꺼내면 되지만, 스택이 비어있다면, 즉,(가 없다면)의 짝이 없다는 뜻이므로 해당 문자열은 VPS가 될 수 없다. 그러므로,)하나를stack에 저장하고 즉시 반복문을 종료한다.
반복문이 종료된 후,stack이 비어있으면 짝이 모두 맞았다는 뜻이므로YES를 출력하고, 비어있지 않다면)가 하나 저장되어 있거나,(이 더 많아 모두 삭제되지 않았다는, 즉, 짝이 맞지 않다는 뜻이므로NO를 출력한다.
import java.io.*;
import java.util.*;
public 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));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
Stack<Character> stack = new Stack<>();
for(int i=0;i<t;i++) {
String str = br.readLine();
for(int j=0;j<str.length();j++) {
if(str.charAt(j) == '(') stack.push('(');
else if(!stack.empty()) stack.pop();
else {
stack.push(')'); break;
}
}
if(stack.empty()) sb.append("YES\n");
else sb.append("NO\n");
stack.clear();
}
bw.write(sb + "");
br.close();
bw.close();
}
}
📌 문제 : 균형잡힌 세상
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호(()) 와 대괄호([])로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호(
()는 오른쪽 소괄호())와만 짝을 이뤄야 한다.- 모든 왼쪽 대괄호(
[)는 오른쪽 대괄호(])와만 짝을 이뤄야 한다.- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
⬇️ 입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호(
()), 대괄호([])로 이루어져 있으며, 온점(.)으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(.)가 들어온다.
⬆️ 출력
각 줄마다 해당 문자열이 균형을 이루고 있으면
yes를, 아니면no를 출력한다.
❗ 힌트
.와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.
💡 코드 : 균형잡힌 세상
✅ 기본적인 알고리즘은 위 문제와 동일하다. 단, 위 문제는 소괄호
()만 취급하였고, 이번 문제에서는 대괄호[]까지 취급한다. 따라서, if ~ else문에 대괄호에 대한 조건을 추가해주기만 하면 해결할 수 있다!
문자열str의j번째 문자를ch에 저장하여,ch가(나[인 경우에는stack에 저장한다.ch가)나]인 경우는 각각 처리해야 하는데, 먼저ch = ')'인 경우에는stack의 꼭대기 요소가(여야만 짝이 맞기 때문에 해당 요소를 꺼낼 수 있다. 즉,stack이 비어있거나, 꼭대기 요소가[라면 짝이 맞지 않다는 뜻이므로)를stack에 넣고 반복문을 종료한다.ch = ']'인 경우에도 마찬가지로stack의 꼭대기 요소가[인 경우에만 해당 요소를 꺼내고,stack이 비어있거나 꼭대기 요소가(라면]를stack에 넣고 반복문을 종료한다.
반복문이 종료되면 위에서 설명한 것과 같이stack이 비어있으면yes를, 비어있지 않다면no를 출력하면 된다.
import java.io.*;
import java.util.*;
public 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));
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
while(true) {
String str = br.readLine();
if(str.equals(".")) break;
for(int j=0;j<str.length();j++) {
char ch = str.charAt(j);
if(ch == '(' || ch == '[') stack.push(ch);
else if(ch == ')') {
if(stack.empty() || stack.peek() != '(') {
stack.push(ch); break;
} else stack.pop();
} else if(ch == ']') {
if(stack.empty() || stack.peek() != '[') {
stack.push(ch); break;
} else stack.pop();
}
}
if(stack.empty()) sb.append("yes\n");
else sb.append("no\n");
stack.clear();
}
bw.write(sb + "");
br.close();
bw.close();
}
}
