[백준(JAVA)] 9012번: 괄호

문제

✔ 난이도 - Silver 4

설명

백준 알고리즘은 스택으로 분류되어있지만 요즘은 덱으로 많이 대체되고 있는 추세라 덱으로 풀었다
https://velog.io/@seha01130/JAVA-덱Deque-정리

처음에는 아래처럼 코드를 작성했는데 그럼 처음 괄호가 ) 라면 뒤를 더 볼 것도 없이 NO가 답임에도 문자열 끝까지 확인해야하므로 비효율적이다.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Deque<Character> deque = new ArrayDeque<>();

        int T = Integer.parseInt(br.readLine());
        String str;
        char[] array;

        for (int i = 0; i < T; i++){
            str = br.readLine();
            array = str.toCharArray();

            for (int j = 0; j < array.length; j++){
                if (deque.isEmpty() || deque.peekLast() == array[j]){
                    deque.addLast(array[j]);
                } else if (deque.peekLast().equals('(') && deque.peekLast() != array[j]) {
                    deque.removeLast();
                }
            }

            if (deque.isEmpty()){
                sb.append("YES");
            } else {
                sb.append("NO");
            }
            deque.clear();

            if (i < T - 1){
            sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

따라서 아래의 조건처럼 다시 코드를 짜주었다.

덱에는 ( 문자만 add 해준다. ( 문자가 오면 무조건 add 한다.
빈 덱일때 ) 문자가 오면 더 볼 것도 없으므로 break; 하고 NO 출력
빈 덱이 아닐때 즉, 덱에 ( 가 존재할때 ) 문자가 오면 remove한다.
하나의 문자열 검토가 끝나면 다음 문자열 검사를 위해 덱을 clear() 해준다.
하나의 문자열 검토가 끝났을 때 덱이 empty이면 YES, 아니면 NO를 출력한다.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Deque<Character> deque = new ArrayDeque<>();

        int T = Integer.parseInt(br.readLine());
        String str;

        for (int i = 0; i < T; i++){
            str = br.readLine();

            for (int j = 0; j < str.length(); j++){
                if (str.charAt(j) == '('){
                    deque.addLast(str.charAt(j));
                } else if (deque.isEmpty() && str.charAt(j) == ')'){
                    deque.addLast(str.charAt(j));
                    break;
                } else {
                    deque.removeLast();
                }
            }

            sb.append(deque.isEmpty() ? "YES" : "NO");
            deque.clear();

            if (i < T - 1){
            sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

TIL💡

📌 문자열 str을 입력받은 후 하나의 문자씩 검사하기위해 str.toCharArray()를 호출하여 char[] array를 만든 후 array.length만큼 루프를 돌렸는데 그냥 문자열str 자체에서 str.length() 만큼 루프를 돌려가며 str.charAt()으로 문자 하나씩 꺼내올 수 있는 방법도 있었다.

📌 삼항 연산자

if (deque.isEmpty()){
	sb.append("YES");
} else {
	sb.append("NO");
}

이렇게 길게 쓰는 것보다
sb.append(deque.isEmpty() ? "YES" : "NO"); 이렇게 삼항 연산자를 써서 한 줄로 끝내는 방법도 있으니 잘 활용하자.