괄호 (백준 9012번)

박영준·2023년 5월 24일
0

코딩테스트

목록 보기
146/300

메모

/*
PS = 괄호 문자열 (, )
VPS = 올바른 괄호 문자열
기본 VPS = ()

예시 1.
x = VPS 일 때
(x) = VPS 이다.

예시 2.
x = VPS, y = VPS 일 때
xy = VPS 이다.

예시 3.
(())() = VPS, ((())) = VPS 일 때
(()( != VPS, (())())) != VPS, (() != VPS 이다
 --> () 이렇게 쌍이 맞지 않기 때문

올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력
*/

해결법

방법 1

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		for (int i = 0; i < T; i++) {
			System.out.println(solve(in.next()));		// nextLine() 은 사용 X
		}
	}
 
	public static String solve(String s) {
    
		Stack<Character> stack = new Stack<>();		// 스택 사용
 
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
 
			if (c == '(') {			// '(' 일 경우 : 스택에 넣는다.
				stack.push(c);
			} else if (stack.empty()) {		// ')' 을 push 한 경우 中 pop할 원소가 없을 경우 : '(' 개수 < ')' 개수 이므로, "NO" 
				return "NO";
			} else {						// ')' 을 push 한 경우 : '(' 개수 == ')' 개수 이므로, 스택의 원소를 반환 및 삭제한다.
				stack.pop();
			}
		}
 
		// stack 의 push, pop 이후
		if (stack.empty()) {		// 스택이 비어있으면, YES -> 온전한 수식이기 때문
			return "YES";
		} else {						// 스택에 잔여 요소가 있으면, '(' 개수 > ')' 개수 이므로, "NO" 
			return "NO";
		}
	}
}
  • scanner

    • nextLine() 대신 next()를 사용하는 이유?
      • nextLine()을 사용하게 되면, 남아있는 공백까지 읽어버리게 된다.
      • 따라서, 공백을 기준으로 문장 한 개만 읽는 next() 가 여기선 옳다.

    참고: Scanner 클래스

  • '(' 를 기준으로 추가적으로 ')'를 붙이는 방식 (3가지 경우)

    1. '(' 개수 == ')' 개수 : 올바른 괄호 문자열

    2. '(' 개수 > ')' 개수 : '(' 가 pop으로 지워지지않아 스택 안에 '(' 가 여전히 남아있게 된다.

    3. '(' 개수 < ')' 개수 : 이미 비어있는 스택에서 pop을 하므로 에러(EmptyStackException) 발생


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


괄호 (백준 9012번)

profile
개발자로 거듭나기!

0개의 댓글