[백준/Java] 9012번 - 괄호

문제 & 난이도

• 스택 구조
• 난이도 : 실버 4

 

풀이

public class beakjoon9012 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();

        for(int i = 0; i < T; i++){
            String sentence = sc.nextLine();

            //stack 구현
            Deque<Character> stack = new ArrayDeque<Character>();

            for(int j = 0; j < sentence.length(); j++){
                //charAt(j) : 문자열에서 j번째 인덱스에 있는 문자를 반환하는 메서드
                if(sentence.charAt(j) == '('){
                    stack.push(sentence.charAt(j));
                }
                //else - 다음 문자가 닫힌 괄호일 경우
                else{
                    //스택이 비어있다면
                    if(stack.isEmpty()){
                        stack.push(sentence.charAt(j));
                        break;
                    }
                    //스택 안에 열린 괄호가 있다면
                    else{
                        stack.pop();
                    }
                }
            }
            if(stack.isEmpty()){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
        }
    }
}

 

: 코딩테스트 스택 구조의 빈출 유형으로, 열린 괄호를 만나면 스택에 넣고 닫힌 괄호를 만나면 스택에서 열린 구조를 빼는 알고리즘. 최종적으로 스택이 비어있다면 yes, 남아있다면 no반환

 

알게 된 것 & 느낀 점 

 

-      top() : 스택의 가장 위에 있는 자료 반환

-      push() : 스택에 자료 삽입

-      pop() : 스택에서 자료 삭제

-      isEmpty() : 스택이 비어있으면 true, 차있으면 false 반환
* pop()과 peek() 메서드를 호출할 때, 스택이 비어 있으면 EmptyStackException이 발생하므로, 사전에 isEmpty() 메서드를 사용해 스택이 비어 있는지 확인하는 것이 좋다

-      isFull() : 스택이 가득 차면 true, 비어있으면 false 반환

 

• 코딩테스트의 기본은 배열을 다루는 것!
• 스택구조를 이용해야 하는 문제는 Stack클래스를 이용하는 것과 Deque인터페이스를 구현한 arrayDeque, LinkedList를 사용하는 방법이 있다.
  • Deque : 이중 끝 큐 구조로, 양쪽 끝에서 요소의 추가와 제거가 모두 가능한 스택과 큐의 기능을 모두 포함한 자료 구조
  • LinkedList : 노드 기반의 이중 연결 리스트로, 삽입 삭제가 용이. 메모리 공간을 연속적으로 할당할 필요 x
  • ArrayDeque : 모리 크기를 자동으로 확장하는 배열을 기반으로 작동하여 빠른 성능