문제

Programmers, 올바른 괄호

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 올바른 괄호쌍을 검사하기 위해 stack을 활용한다. 여는 문자일 때는 해당 문자를 스택에 푸시하고, 닫는 문자일 때는 스택 상단의 원소가 여는 문자인지 확인한다. 닫는 문자만 남았을 수도 있기에 최종적으로 스택이 비어있는지 검사한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string str)
{
    stack<char> s;
    for (auto e : str) {
        if (e == '(')
            s.push(e);
        else {
            if (s.empty() || s.top() == ')') 
                return false;
            s.pop();
        }
    }
    return s.empty();
}

Java

import java.util.*;

class Solution {
    boolean solution(String str) {
        boolean answer = true;
        Stack<Character> s = new Stack<>();
        for (var e : str.toCharArray()) {
            if (e == '(') {
                s.push(e);
                continue;
            }
            if (s.isEmpty() || s.peek() == ')')
                return false;
            s.pop();
        }
        return s.isEmpty();
    }
}

태그 - algorithm, hash(사용한 자료구조), boj(플랫폼)