[JAVA] BOJ 9012 괄호

 

스택을 이용해서 푸는 문제이다. Stack은 LIFO구조로 한쪽 끝이 막혀있는 병을 생각하면 된다. 이 문제의 경우 입력값으로 들어오는 괄호를 병(스택)에 넣기 전에 병에 가장 마지막에 들어가 있는 괄호와 더해 () 즉 VPS 인지 검사한 다음 만약 VPS라면 병에 들어있는 마지막 괄호를 제거해주고 아니라면 병에 넣어주면 된다. 

 

INPUT/OUTPUT 에는 BufferedReader/BufferedWriter 를 사용하였다. 

 

import java.io.*;
import java.util.*;


public class Main {
	public static long[] N_li = new long[101];
	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());
		StringTokenizer st;
		for (int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			ArrayList<String> arr = new ArrayList<>();
			String vps = st.nextToken();
			for(int j=0; j<vps.length(); j++) {
				String letter = String.valueOf(vps.charAt(j));
				if(arr.size()==0) arr.add(letter);
				else {
					if ((arr.get(arr.size()-1)+letter).equals("()")) {
						arr.remove(arr.size()-1);
					}else arr.add(letter);
				}
			}
			if (arr.size()>=1) {
				bw.write("NO");
			}else bw.write("YES");
			bw.newLine();
		}
		bw.flush();
		bw.close();
	}
}

 

Stack 구현에 ArrayList 데이터 타입을 사용하였다. 입력값으로 들어오는 괄호뭉탱이(?)를 잘 잘라서 스택에 넣는 것이 중요했는데 이는 괄호들을 하나의 String객체(vps)로 받은 다음 charAt 메서드를 사용하여 하나씩 잘랐다. 만약 스택이 비어있으면 괄호를 바로 대입해주고 아니라면 스택의 마지막 괄호와 새로운 괄호가 VPS 인지 확인하는 과정을 거쳐 VPS라면 스택의 마지막 괄호를 삭제하고 아니라면 대입했다. 

이후 스택이 비어있으면 모든 괄호가 짝이 맞았다는 뜻이므로 NO를 출력하고 아니면 YES를 출력하였다.

 

예상치 못한 에러가 있었는데 arr.get(arr.size()-1)+letter == "()"라고 하면 아무리 VPS여도 false를 리턴하였다. 찾아보니 == 연산자는 객체가 저장되어 있는 주소 값을 불러오는데 equals 메서드는 내용을 불러온다고 한다. 이는 Call By Reference, Call By Value 개념이라고 한다. 어찌 됐든 String 객체의 문자열을 비교할 때는 equals를 사용해야겠다.