Vienna
백준9012번) 괄호 본문
https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
◇ 문제
괄호 문자열(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”를 한 줄에 하나씩 차례대로 출력해야 한다.
◆ 풀이
일단 문제를 단순하게 생각해보자.
(는 0, )는 1로 가정.
0을 넣는 수 만큼 1도 집어넣으면 되는 것이다.
010101 => 정상.
그렇다면 Stack 1개를 준비하고, 기대값을 저장해놓는 Stack으로 사용하는 건 어떨까?
(를 만날 때마다 기대값 Stack에도 1을 집어넣는 것이다.
그리고 실제로 ")"을 만나게 될 때마다 기대값 Stack에서 1씩 제거해나가는 것이다.
그런데 만약 기대값 Stack에서 빼낼 수 없는 Empty 상태인데 1을 빼내려 한다면 이 때에는 더이상 확인할 필요 없이 NO를 출력하면 된다.
그리고 최종적으로 모든 문자열 탐색이 끝났을 때 기대값 Stack이 비어있지 않은 경우에도 NO를 출력하면 되고, 그게 아니라면 YES다.
구상이 끝났으므로 맞춰 코드를 작성해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(int i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
String[] result = new String[iMax];
Stack<Integer> checkSt = new Stack<>();
for(int i=0; i<iMax; i++){
String str = input[i];
checkSt.clear();
for(int j=0, jMax = str.length(); j<jMax; j++){
if(pushable(str.charAt(j))){
// 구상 과정에서 굳이 1일 이유가 없어서 0으로 바꾸었다.
checkSt.push(0);
}
else if (checkSt.isEmpty()){
result[i] = "NO";
break;
}
else{
checkSt.pop();
}
}
if(result[i]==null){
result[i] =checkSt.isEmpty() ? "YES" : "NO";
}
}
for(int i=0; i<iMax; i++){
System.out.println(result[i]);
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
메모리 사용량이 좀 많은가?
싶어서 int를 미리 캐싱하고 Byte로 바꿔보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
String[] result = new String[iMax];
Stack<Byte> checkSt = new Stack<>();
for(i=0; i<iMax; i++){
String str = input[i];
checkSt.clear();
for(int j=0, jMax = str.length(); j<jMax; j++){
if(pushable(str.charAt(j))){
byte b = 0;
checkSt.push(b);
}
else if (checkSt.isEmpty()){
result[i] = "NO";
break;
}
else{
checkSt.pop();
}
}
if(result[i]==null){
result[i] =checkSt.isEmpty() ? "YES" : "NO";
}
}
for(i=0; i<iMax; i++){
System.out.println(result[i]);
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
String배열을 재사용해볼까?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
Stack<Byte> checkSt = new Stack<>();
for(i=0; i<iMax; i++){
String str = input[i];
input[i]= null;
checkSt.clear();
for(int j=0, jMax = str.length(); j<jMax; j++){
if(pushable(str.charAt(j))){
byte b = 0;
checkSt.push(b);
}
else if (checkSt.isEmpty()){
input[i] = "NO";
break;
}
else{
checkSt.pop();
}
}
if(input[i]==null){
input[i] =checkSt.isEmpty() ? "YES" : "NO";
}
}
for(i=0; i<iMax; i++){
System.out.println(input[i]);
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
아무래도 String str = input[i]할 때 이미 새로 생성서 그런 것 같다.
다시 수정해보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
String[] result = new String[iMax];
Stack<Byte> checkSt = new Stack<>();
for(i=0; i<iMax; i++){
checkSt.clear();
for(int j=0, jMax = input[i].length(); j<jMax; j++){
if(pushable(input[i].charAt(j))){
byte b = 0;
checkSt.push(b);
}
else if (checkSt.isEmpty()){
result[i] = "NO";
break;
}
else{
checkSt.pop();
}
}
if(result[i]==null){
result[i] =checkSt.isEmpty() ? "YES" : "NO";
}
}
for(i=0; i<iMax; i++){
System.out.println(result[i]);
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
이번엔 "YES"와 "NO"를 미리 캐싱해보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
private static String _yes = "YES";
private static String _no = "NO";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
String[] result = new String[iMax];
Stack<Byte> checkSt = new Stack<>();
for(i=0; i<iMax; i++){
checkSt.clear();
for(int j=0, jMax = input[i].length(); j<jMax; j++){
if(pushable(input[i].charAt(j))){
byte b = 0;
checkSt.push(b);
}
else if (checkSt.isEmpty()){
result[i] = _no;
break;
}
else{
checkSt.pop();
}
}
if(result[i]==null){
result[i] =checkSt.isEmpty() ? _yes : _no;
}
}
for(i=0; i<iMax; i++){
System.out.println(result[i]);
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
다른 사람들은 어떻게 풀었을까 해서 참고해보니 Stack을 사용하지 않고 int만으로 풀었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
private static String _yes = "YES";
private static String _no = "NO";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i, cnt;
boolean printed;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
st = new StringTokenizer(br.readLine());
input[i] = st.nextToken();
}
for(i=0; i<iMax; i++){
cnt = 0;
printed = false;
for(int j=0, jMax = input[i].length(); j<jMax; j++){
if(pushable(input[i].charAt(j))){
cnt++;
}
else if (cnt==0){
System.out.println(_no);
printed = true;
break;
}
else{
cnt--;
}
}
if(!printed){
System.out.println(cnt==0 ? _yes : _no);
}
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
드라마틱하게 줄어들 것이라 기대한 것과는 달라 살짝 아쉽다.
이번엔 다른 분의 조언을 받아 tokenizing하지 않고 받아와보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {
private static String _yes = "YES";
private static String _no = "NO";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int i, cnt;
boolean printed;
int iMax = Integer.parseInt(st.nextToken());
String[] input = new String[iMax];
for(i=0; i<iMax; i++){
input[i] = br.readLine();
}
for(i=0; i<iMax; i++){
cnt = 0;
printed = false;
for(int j=0, jMax = input[i].length(); j<jMax; j++){
if(pushable(input[i].charAt(j))){
cnt++;
}
else if (cnt==0){
System.out.println(_no);
printed = true;
break;
}
else{
cnt--;
}
}
if(!printed){
System.out.println(cnt==0 ? _yes : _no);
}
}
}
public static boolean pushable(Character c){
return c == '(' ? true : false;
}
}
'알고리즘 문제 풀이' 카테고리의 다른 글
| 백준10807번) 개수 세기 (1) | 2023.05.16 |
|---|---|
| 백준2830번) 행성 X3 (0) | 2023.05.16 |
| 프로그래머스) 숫자 문자열과 영단어 (0) | 2023.05.16 |
| 프로그래머스) 짝수는 싫어요 (0) | 2023.05.15 |
| 백준24174번)알고리즘 수업 - 힙 정렬 2 (0) | 2023.05.14 |
'알고리즘 문제 풀이' Related Articles
more
Comments