[프로그래머스 / Java] 코딩테스트 연습: 올바른 괄호 (스택 / 큐)

난이도: Level 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

---

 

이 문제가 스택/큐 알고리즘이라는 것을 몰랐다면 나는 문자열로만 돌리다가 시간을 꽤 많이 잡아먹었을 것이다.

하지만 스택/큐 문제라는 것을 알려주니까 내 생각보다 꽤 빨리 풀었다.

어떤 알고리즘으로 접근해야 하는지 파악하는 것이 참 중요한 것 같다.

 

우선 큐와 스택을 선언한다.

 

    Queue<Character> queue = new LinkedList<>();    // 문자열 s에 속한 문자들을 차례대로 담아놓은 큐

    Stack<Character> stack = new Stack<>();         // 올바른 괄호 검사를 위한 임시 스택

 

 

큐에는 문자열 s에 있는 문자들을 하나씩 차례대로 담는다.

 

    // 문자열 s에 속한 문자들을 큐에 차례대로 추가

    for (char c : s.toCharArray()) {

        queue.add(c);

    }

 

 

큐에 있는 문자를 차례로 꺼내서 모두 검사할 것이다.

스택의 맨 위에 있는 문자와 큐에서 방금 꺼낸 문자를 합친 문자열이 "()"가 되어야 하는데, 결국 이것의 의미는 스택의 맨 위에 있는 문자는 무조건 '('가 되어야 한다는 뜻이다.

그래서 만약 스택이 비어있다면 처음에는 큐에서 꺼낸 문자를 스택에 넣어야만 하는데, 큐에서 꺼낸 문자가 ')'이고 이 문자를 맨 처음부터 스택에 넣으려고 한다면, 위의 문장에서 검사할 문자열은 ')'로 시작할 수밖에 없으므로 절대로 올바른 괄호가 될 수 없다. 

그러므로 스택이 비어있을 때 넣으려고 하는 문자가 ')'라면 더 검사할 필요 없이 바로 false를 리턴하면 된다.

 

    // 큐가 빌 때까지(문자열 s를 모두 검사할 때까지) 반복

    while (!queue.isEmpty()) {

        char now = queue.poll();    // 현재 문자를 큐에서 꺼내기

       

        if (!stack.isEmpty()) {     // 스택이 비어있지 않다면

            char before = stack.peek();     // 스택의 맨 위에있는 문자

           

            // 스택의 맨 위에있는 문자와 큐에서 꺼낸 문자를 합친 문자열이 "()"와 같다면

            if ((String.valueOf(before) + String.valueOf(now)).equals("()")) {

                stack.pop();        // 스택의 맨 위에 있는 문자를 꺼내기

            } else {  // 그렇지 않다면

                stack.push(now);    // 큐에서 꺼낸 문자를 스택에 추가

            }

        } else {    // 스택이 비어있다면

            if (now == ')') {   // 스택에 처음 넣을 문자가 ')'라면

                return false;   // 문자열 s는 절대로 올바른 괄호가 될 수 없음

            } else {    // 그렇지 않다면

                stack.push(now);        // 큐에서 꺼낸 문자를 스택에 추가

            }

        }

    }

 

 

위에서 문자열 s를 모두 검사했는데도 스택이 비어있지 않다면, 모든 괄호들이 () 묶음으로 나누어 떨어지지 못한 것이므로 false를 리턴해준다.

만약 이 모든 검사를 통과했다면 문자열 s는 올바른 문자열이 되는 것이므로 true를 리턴해주면 된다.

 

    if (!stack.isEmpty()) {     // 문자열 s를 모두 검사했지만 스택이 비어있지 않다면

        return false;           // 문자열 s는 올바른 괄호가 아님

    }

    return true;      // 위의 검사들을 모두 통과했다면 문자열 s는 올바른 괄호

 

 

로직 예시

s = "(()("

초기 queue = ( ( ) (

초기 stack = 

---------------------------큐가 비어있지 않으므로 while문 시작-------------------------

큐에서 문자를 꺼내기

now = queue.poll() = (

 

스택이 비어있음

큐에서 꺼낸 문자가 ')'가 아니므로 스택에 삽입

stack.push(now)

스택에 ( 삽입

------------------------------------------while문 종료------------------------------------------

현재 queue = ( ) (

현재 stack = (

---------------------------큐가 비어있지 않으므로 while문 시작-------------------------

큐에서 문자를 꺼내기

now = queue.poll() = (

 

스택이 비어있지 않음

스택의 맨 위에 있는 문자 확인

before = stack.peek() = (

스택의 맨 위에 있는 문자와 큐에서 꺼낸 문자를 합친 문자열이 "()"와 같은지 확인

before + now = ((

"()"와 다르므로 큐에서 꺼낸 문자를 스택에 삽입

stack.push(now)

스택에 ( 삽입

------------------------------------------while문 종료------------------------------------------

현재 queue = ) (

현재 stack = ( (

---------------------------큐가 비어있지 않으므로 while문 시작-------------------------

큐에서 문자를 꺼내기

now = queue.poll() = )

 

스택이 비어있지 않음

스택의 맨 위에 있는 문자 확인

before = stack.peek() = (

스택의 맨 위에 있는 문자와 큐에서 꺼낸 문자를 합친 문자열이 "()"와 같은지 확인

before + now = ()

"()"와 같으므로 스택의 맨 위에 있는 문자를 꺼내기

stack.pop()

스택에서 ( 제거

------------------------------------------while문 종료------------------------------------------

현재 queue = (

현재 stack = (

---------------------------큐가 비어있지 않으므로 while문 시작-------------------------

큐에서 문자를 꺼내기

now = queue.poll() = (

 

스택이 비어있지 않음

스택의 맨 위에 있는 문자 확인

before = stack.peek() = (

스택의 맨 위에 있는 문자와 큐에서 꺼낸 문자를 합친 문자열이 "()"와 같은지 확인

before + now = ((

"()"와 다르므로 큐에서 꺼낸 문자를 스택에 삽입

stack.push(now)

스택에 ( 삽입

------------------------------------------while문 종료------------------------------------------

현재 queue = 

현재 stack = ((

-----------------------------큐가 비어있으므로 while문 종료-----------------------------

스택이 비어있지 않으므로 false 리턴

---

전체 코드

import java.util.*;
 
class Solution {
    boolean solution(String s) {
        Queue<Character> queue = new LinkedList<>();    // 문자열 s에 속한 문자들을 차례대로 담아놓은 큐
        Stack<Character> stack = new Stack<>();         // 올바른 괄호 검사를 위한 임시 스택
        
        // 문자열 s에 속한 문자들을 큐에 차례대로 추가
        for (char c : s.toCharArray()) {
            queue.add(c);
        }
        
        // 큐가 빌 때까지(문자열 s를 모두 검사할 때까지) 반복
        while (!queue.isEmpty()) {
            char now = queue.poll();    // 현재 문자를 큐에서 꺼내기
            
            if (!stack.isEmpty()) {     // 스택이 비어있지 않다면
                char before = stack.peek();     // 스택의 맨 위에있는 문자
                
                // 스택의 맨 위에있는 문자와 큐에서 꺼낸 문자를 합친 문자열이 "()"와 같다면
                if ((String.valueOf(before) + String.valueOf(now)).equals("()")) {
                    stack.pop();        // 스택의 맨 위에 있는 문자를 꺼내기
                } else {  // 그렇지 않다면
                    stack.push(now);    // 큐에서 꺼낸 문자를 스택에 추가
                }
            } else {    // 스택이 비어있다면
                if (now == ')') {   // 스택에 처음 넣을 문자가 ')'라면 
                    return false;   // 문자열 s는 절대로 올바른 괄호가 될 수 없음
                } else {    // 그렇지 않다면
                    stack.push(now);        // 큐에서 꺼낸 문자를 스택에 추가
                }
            }
        }
        
        if (!stack.isEmpty()) {     // 문자열 s를 모두 검사했지만 스택이 비어있지 않다면
            return false;           // 문자열 s는 올바른 괄호가 아님
        }
 
        return true;      // 위의 검사들을 모두 통과했다면 문자열 s는 올바른 괄호
    }
}