BOJ(백준 온라인 저지) 9012번 with 자바[JAVA]

https://www.acmicpc.net/problem/9012

9012번: 괄호

---

 

처음에는 여는 괄호의 개수와 닫는 괄호의 개수가 같으면 올바른 괄호 문자열인줄 알았다.

 

코드를 보자.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		int openCount = 0;
		int closeCount = 0;
		
		for(int i=0; i<T; i++) {
			
			String str = br.readLine();
			
			for(int j=0; j<str.length(); j++) {
				
				char ch = str.charAt(j);
				
				if(ch == '(')
					openCount++;
				else if(ch == ')')
					closeCount++;
				
			}
			
			if(openCount == closeCount)
				sb.append("YES").append("\n");
			else
				sb.append("NO").append("\n");
			
		}
		
 	}
}

 

하지만 틀렸다.

 

예시를 들어보자.

만약 괄호가 "( ) ) ( ( )" 와 같이 주어졌다고 해보자.

 

결과는 NO이다 3번째 괄호가 짝이 없는 닫힌 괄호이기 때문이다.

하지만 위의 코드를 실행하면 YES라고 나온다. 닫는 괄호의 개수와 여는 괄호의 총 개수가 같기 때문이다.

 

여는 괄호의 개수와 닫는 괄호의 개수가 같다는 것은 (올바른 괄호 문자열)VPS의 필요조건이지 충분조건이 아니었다.

 

어떤 과정을 추가해주어야할까,,,?

 

위에 코드는 3번째 괄호에서 NO를 판단해주지 못한다.

그렇다면 3번째 괄호에서 어떻게 NO를 판단해줄까?

 

3번째 괄호는 그 괄호에 대응하는 여는 괄호가 없다는 특징을 가지고 있다.

그렇다면 괄호들을 하나하나 읽어들일때마다 여는 괄호의 개수와 닫는 괄호의 개수를 비교해주면...?

 

코드를 보자.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			
			int openCount = 0;
			int closeCount = 0;
			
			String str = br.readLine();
			
			for(int j=0; j<str.length(); j++) {
				
				char ch = str.charAt(j);
				
				 /* 
				 * 여는 괄호가 추가될 때 openCount와 closeCount를 비교하지 않는 이유는
				 * 여는 괄호와 짝이 되는 닫는 괄호가 그 뒤에 나올 수 있기 때문에
				 * 여는 괄호가 추가될 때 체크하는게 아니라
				 * 모든 괄호를 받고 나서 마지막에 체크하는것이다.
				 */
				
				if(ch == '(')
					openCount++;
				else if(ch == ')') {
					closeCount++;
					
				/*
				 * 닫힌 괄호가 추가될 경우, 그 짝에 해당하는 여는 괄호가 없다면 VPS가 아니다.
				 * 그 짝이 있는지 없는지는 openCount를 보면 된다.
				 * 닫힌 괄호가 추가됨으로 인해 closeCount가 openCount보다 많아졌다면,
				 * 추가된 닫힌 괄호와 짝이 되는 여는 괄호가 없다는 말이다.
				 * 따라서 이 경우는 닫힌 괄호가 여는 괄호보다 더 많아서 VPS가 되지 못하는 경우이다.
				 */
					
					if(openCount < closeCount) {
						sb.append("NO").append("\n");
						break;
					}
				}
				
			}
			
			// 끝까지 확인 했을 때 닫는 괄호의 개수와 여는 괄호의 개수가 같다는 것은 VPS라는 의미
			if(openCount == closeCount)
				sb.append("YES").append("\n");
			// 여는 괄호가 닫는 괄호보다 많아서 VPS가 되지 못하는 경우이다.
			else if(openCount > closeCount)
				sb.append("NO").append("\n");
			
		}
		
		System.out.println(sb);
		
 	}
}

 

 

정답!!

 

 

이 코드를 스택 자료구조를 통해 조금 더 섹시하게 바꿔보자.

 

https://st-lab.tistory.com/178

[백준] 9012번 : 괄호 - JAVA [자바]

내가 정말 좋아하는 블로그이다. 들어가서 확인해보자.

위에 블로그에서는 Stack을 활용하여 문제를 풀었다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			
			// flag가 true이면 YES, false이면 NO
			boolean flag = true;
			
			Stack<Character> stack = new Stack<>();
			
			String str = br.readLine();
			
			for(int j=0; j<str.length(); j++) {
				
				char ch = str.charAt(j);
				
				if(ch == '(') 
					stack.add('(');
				else {
					
					// 단는 괄호가 많은 경우(여는 괄호가 부족한 경우) 에서의 예외처리
					if(stack.isEmpty()) {
						sb.append("NO").append("\n");
						flag = false;
						break;
					}else
						stack.pop();
					
				}
				
			}
			
			// 닫는 괄호가 부족한 경우(여는 괄호가 많은 경우) 에서의 예외처리
			if(!stack.isEmpty()) {
				sb.append("NO").append("\n");
				flag = false;
			}
			
			if(flag)
				sb.append("YES").append("\n");
			
		}
		
		System.out.print(sb);
 	}
}