백준 | 9012 : 괄호 (Java)

usuyn·2021년 9월 14일

알고리즘

목록 보기

10/12

문제에 대한 자세한 정보는 백준 | 9012번 : 괄호에서 확인할 수 있다.

풀이

2가지 방법으로 풀어봤다. 하나는 Stack을 사용하는 방법, 하나는 '(', ')' 개수를 세며 푸는 방법이다.

Stack 사용

Character type Stack을 생성한다.
맨 앞의 문자가 ')' 이거나 맨 뒤의 문자가 '(' 이면 바로 "NO"를 출력한다.
2번에 해당하지 않는 경우, 입력받은 문자열을 charAt(i)을 사용해 검사한다. 검사를 위해 boolean type vps(변수)를 선언하고 true로 초기화한다. 아래는 반복문 과정이다.
3-1. '(' 이면 stack에 push한다.
3-2. ')' 이고 stack이 비어있지 않다면 pop을 통해 '(' 문자를 stack에서 꺼낸다.
3-3. ')' 이고 stack이 비어있다면(짝이 맞지 않는 것) VPS가 아니므로 vps값을 false로 설정하고 break해 반복문을 종료한다.
vps가 true, stack이 비어있다면 "YES"를 출력한다. 이 경우가 아니라면 "NO"를 출력한다.
입력받은 문자열마다 2, 3번 과정을 거친다.

vps 변수가 없고 4번에서 stack이 비어있다. 조건만 있으면 "( ( ) ) )" 이 경우에 3-3에서 break되지만 stack은 비어있는게 맞기 때문에 4번에서 "YES"가 출력된다. 따라서 vps 변수를 선언해서 추가 조건을 만들어줬다.

'(', ')' 개수 세기

'(' 개수를 세는 cnt_l, ')' 개수를 세는 cnt_r 변수를 선언한다.
맨 앞의 문자가 ')' 이거나 맨 뒤의 문자가 '(' 이면 바로 "NO"를 출력한다.
2번에 해당하지 않는 경우, 입력받은 문자열을 charAt(i)을 사용해 검사한다. 아래는 반복문 과정이다.
3-1. '(' 이면 cnt_l의 값을 1 증가시킨다.
3-2. ')' 이면 cnt_r의 값을 1 증가시킨다.
3-3. cnt_l < cnt_r이면 짝이 맞지 않는 것이므로 break해 반복문을 종료한다.
cnt_l == cnt_r이면 "YES"를 출력한다. 이 경우가 아니라면 "NO"를 출력한다.
입력받은 문자열마다 2, 3번 과정을 거친다.

소스코드

Stack 사용

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));

		int N = Integer.parseInt(br.readLine());
		Stack<Character> stack;
		
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			boolean vps = true;
			stack = new Stack<>();

			if (temp.charAt(0) == ')' || temp.charAt(temp.length() - 1) == '(') {
				bw.write("NO\n");
				continue;
			}

			for (int j = 0; j < temp.length(); j++) {
				if (temp.charAt(j) == '(') {
					stack.push('(');
				} else {
					if (!stack.empty()) {
						stack.pop();
					} else {
						vps = false;
						break;
					}
				}
			}

			if (vps && stack.empty()) {
				bw.write("YES\n");
			} else {
				bw.write("NO\n");
			}
		}

		br.close();
		bw.close();
	}
}

'(', ')' 개수 세기

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));

		int N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			int cnt_l = 0;
			int cnt_r = 0;

			if (temp.charAt(0) == ')' || temp.charAt(temp.length() - 1) == '(') {
				bw.write("NO\n");
				continue;
			}

			for (int j = 0; j < temp.length(); j++) {
				if(temp.charAt(j) == '(')
					cnt_l++;
				else if(temp.charAt(j) == ')')
					cnt_r++;
				if(cnt_l < cnt_r) {
					break;
				}
			}
			
			if(cnt_l == cnt_r)
				bw.write("YES\n");
			else
				bw.write("NO\n");
		}

		br.close();
		bw.close();
	}
}