자료구조-괄호문제

문제풀이

알맞은 괄호 수식의 원리를 알면 쉽게 풀 수 있는 문제였다. 원리는 여는 괄호가 '('가 있으면 반드시 이에 대응하는 닫는 괄호 ')'가 있어야한다는 것이다. 이것을 Stack을 이용하여 풀면 간단하게 해결할 수 있다. 여는 괄호가 있을 때는 스택에 추가하고 닫는 괄호가 있으면 여는 괄호를 하나씩 지워주면 된다.

1. 여는 괄호와 닫는 괄호가 올바른 경우 - 최종적으로 스택에는 아무것도 존재하지 않을 것이다. 고로 YES를 출력해준다.
2. 스택에 괄호가 남는 경우 - 여는 괄호가 많은 경우로 VPS가 아니므로 NO를 출력해준다.
3. 스택에 지울 여는 괄호가 부족한 경우 - 닫는 괄호가 많은 경우로 VPS가 아니므로 NO를 출력해준다.

소스 코드

package data_structure;

import java.util.*;

public class parenthesis {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		
		for(int i =0; i<n; i++) {
			System.out.println(solve(in.next()));
			
		}
		
		

	}
	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.isEmpty()) {
				return "NO";
			}
			else
				stack.pop();
		}
		if(stack.isEmpty()) {
			return "YES";
		}
		else
			return "NO";
	}

}

문제를 풀고 느낀점

• 스택에 대해 다시 한번 생각할 시간을 가지게 되었고, 스택을 어느 상황에 어떻게 활용해야하는지 정확히 알 수 있게 되었다. 스택을 사용하면 편리한 상황이 나올 때 잘 활용할 수 있을 것 같다.