[백준] no9012: 괄호

문제

: 각 줄에 임의의 순서와 갯수로 된 괄호가 주어진다.

: VPS란 () 요렇게 맞게 잘 닫히는 것

: 해당 줄의 괄호가 열고 닫히는게 순서랑 짝이 안맞으면 "NO'

: 잘 맞아 떨어지면 "YES"

 

문제 링크 : https://www.acmicpc.net/problem/9012

---

원리

: VPS 맞추기

---

풀이방법

1. 입력된 괄호를 char배열로 바꾼다.

2. Deque 혹은 Stack을 준비한다.

3. char 배열을 차례로 순회할 것이다.

4. 만약 '('가 나오면 일단 넣어

5. 만약 ')'가 나오고 Deque가 비었으면 '('가 없는 거니 NO 인걸로 체크하고 반복그만~

6. 만약 ')'가 나오고 Dequed에 맨 마지막에 넣은게 '('면 같이 제끼부러~

7. 순회가 다 끝나고,

    Deque에 뭐가 남아 있으면 짝이 안맞는거니 NO 

    순회중에 순서가 안맞았으면 NO

    그 외엔 YES

---

나의 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no9012 {

    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 T = Integer.parseInt(br.readLine());

        for(int i=0; i<T ; i++) {
            char arr[] = br.readLine().toCharArray();
            Deque<Character> dq = new ArrayDeque<>();
            boolean result= false;
            for(int j=0 ; j<arr.length ; j++) {
                if(arr[j]=='(') dq.addLast('(');
                else if (arr[j]==')' && dq.isEmpty()) {
                    result = true;
                    break;
                }
                else if (arr[j]==')' && dq.peekLast()=='(') dq.pollLast();
            }
            if(!dq.isEmpty()) bw.write("NO\n");
            else if(result) bw.write("NO\n");
            else bw.write("YES\n");
        }
        bw.close();
    }
}

 

---

레퍼런스 코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cases = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		int cnt = 0, j = 0;
		
		for(int i = 0; i < cases; i++) {
			char arr[] = br.readLine().toCharArray();
			if(arr[0]==')') sb.append("NO\n");
			else {
				for(j = 0; j < arr.length; j++) {
					if(arr[j] == '(') cnt ++;
					if(arr[j] == ')') cnt --;
					
					if(cnt < 0) {
						sb.append("NO\n");
						break;
					}
				}
				
				if(j == arr.length) {
					if(cnt == 0) sb.append("YES\n");
					else sb.append("NO\n");
				}
				
				cnt = 0;
			}
		}
		
		System.out.println(sb);
	}

}