[스택] 코딩테스트 문제 TIL (괄호) - 백준 9012번

오늘 문제는 스택 자료 구조 유형의 문제에서 기본?이 되는 괄호 문제입니다.

오늘도 집중해봅시다!

---

1. 오늘의 학습 키워드

• 스택
• 문자열

---

2. 문제: 괄호 (9012번)

• 단계: 🥈실버 4티어
• 알고리즘 분류: 자료 구조, 문자열, 스택
• 출처: https://www.acmicpc.net/problem/9012

괄호

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	221883	105294	75518	46.177%

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력 1 복사

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 복사

NO
NO
YES
NO
YES
NO

예제 입력 2 복사

3
((
))
())(()

예제 출력 2 복사

NO
NO
NO

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2012 G번

• 데이터를 만든 사람: baekjoon
• 데이터를 추가한 사람: jh05013
• 문제의 오타를 찾은 사람: marona

알고리즘 분류

• 자료 구조
• 문자열
• 스택

---

3. 나의 풀이

문제 이해 및 접근

이번 문제는 괄호 문자열이 올바른 괄호 문자열(VPS, Valid Parenthesis String)인지 판단하는 문제입니다. 주어진 문자열이 올바른 VPS인지 판단하기 위해서는 괄호의 열림과 닫힘이 올바르게 짝지어져야 합니다.

이 문제를 해결하기 위해 두 가지 접근 방식을 사용했습니다:

1. 스택(Stack)을 활용한 방법: 괄호가 올바르게 짝지어졌는지를 스택을 이용해 확인합니다.
2. 카운팅(Counting)을 이용한 방법: 열림 괄호 (와 닫힘 괄호 )의 개수를 추적하여 올바른 괄호 문자열인지 확인합니다.

첫 번째 풀이: 스택을 활용한 방법

스택을 사용하여 괄호의 짝을 맞추는 방법입니다. 열림 괄호 (는 스택에 추가하고, 닫힘 괄호 )는 스택에서 마지막으로 추가된 열림 괄호와 짝을 맞춰 제거합니다. 만약 닫힘 괄호를 처리할 때 스택이 비어 있다면, 이는 올바르지 않은 문자열로 판단합니다.

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    ps = sys.stdin.readline().strip()
    stack = []
    for i in ps:
        if i == '(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                stack.append(i)
                break

    if len(stack):
        print('NO')
    else:
        print('YES')

• 작동 원리:
  • (가 나오면 스택에 추가하고, )가 나오면 스택에서 (를 제거합니다.
  • 만약 )를 처리할 때 스택이 비어 있으면 올바르지 않은 괄호 문자열로 판단하고 반복을 중단합니다.
  • 최종적으로 스택이 비어 있으면 모든 괄호가 짝지어져 있으므로 YES를 출력하고, 그렇지 않으면 NO를 출력합니다.

시간 복잡도 분석

• T: 테스트 케이스의 수
• 각 테스트 케이스에서 ps의 길이를 N이라고 할 때, 각 테스트 케이스에서 반복문은 N번 수행됩니다.
• 스택에 값을 추가하거나 제거하는 연산(append, pop)은 O(1) 시간 복잡도를 가집니다.

따라서, 각 테스트 케이스에 대해 반복문이 N번 수행되므로, 각 테스트 케이스에 대한 시간 복잡도는 $O(N)$입니다.

전체적으로 T개의 테스트 케이스에 대해 이 작업이 반복되므로, 전체 시간 복잡도는 $O(T * N)$입니다.

두 번째 풀이: 카운팅을 이용한 방법

이 방법에서는 스택 대신 total 변수로 열림 괄호와 닫힘 괄호의 균형을 추적합니다. 열림 괄호 (가 나오면 total을 증가시키고, 닫힘 괄호 )가 나오면 total을 감소시킵니다.

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    ps = sys.stdin.readline().strip()

    total = 0

    for i in ps:
        if i == '(':
            total += 1
        else:
            total -= 1

        if total < 0:
            print("NO")
            break

    if total > 0:
        print("NO")
    elif total == 0:
        print('YES')

• 작동 원리:
  • total 변수는 열림 괄호 (의 개수와 닫힘 괄호 )의 개수 차이를 기록합니다.
  • total이 0보다 작아지면 이미 닫힘 괄호가 너무 많아졌다는 의미이므로 그 즉시 NO를 출력하고 반복을 중단합니다.
  • 모든 반복이 끝난 후 total이 0이면 올바른 괄호 문자열이므로 YES를 출력하고, 그렇지 않으면 NO를 출력합니다.

시간 복잡도 분석

• T: 테스트 케이스의 수
• 각 테스트 케이스에서 ps의 길이를 N이라고 할 때, 각 테스트 케이스에서 반복문은 N번 수행됩니다.
• 각 반복문 내부의 조건문(if) 및 변수 연산은 O(1) 시간 복잡도를 가집니다.

따라서, 각 테스트 케이스에 대한 시간 복잡도는 $O(N)$입니다.

전체적으로 T개의 테스트 케이스에 대해 이 작업이 반복되므로, 전체 시간 복잡도는 $O(T * N)$입니다.

하지만! 실질적인 속도는 카운팅을 이용한 방법이 더 빠를것입니다.

그 이유는 다음과 같습니다:

1. 메모리 접근과 관리:

• 카운팅 방법: 이 방법에서는 단순히 정수 하나(total)를 사용하여 카운팅합니다. 이 변수는 CPU 캐시에서 관리될 수 있기 때문에 접근 속도가 매우 빠릅니다.
• 스택 방법: 이 방법에서는 리스트를 사용하여 스택을 구현합니다. 리스트의 크기가 커지면 메모리 관리 비용이 증가할 수 있으며, 스택에서 append와 pop 연산이 자주 일어나게 됩니다. 이러한 연산들은 개별적으로는 O(1)이지만, 메모리 할당이나 리스트 크기 증가에 따라 약간의 오버헤드가 발생할 수 있습니다.

2. 연산 간소화:

• 카운팅 방법: 단순히 total 변수에 더하고 빼는 연산만을 수행하므로, 연산 자체가 매우 간단합니다.
• 스택 방법: 스택의 경우, append와 pop 연산이 필요하며, 스택의 상태를 계속 관리해야 합니다. 비록 각 연산이 O(1)이라 하더라도, 실제 실행 시의 오버헤드는 카운팅 방법보다 클 수 있습니다.

3. 조건문 처리:

• 카운팅 방법: total 값이 음수가 되는 순간 바로 NO를 출력하고 반복을 종료할 수 있습니다. 이 경우, 루프를 조기에 종료하여 불필요한 연산을 줄일 수 있습니다.
• 스택 방법: 스택을 이용할 때도 중간에 조기 종료가 가능하지만, 스택의 크기를 체크하고 pop할 때 발생하는 추가 연산이 필요합니다.

결론:

• 이론적인 시간 복잡도는 동일하게 $O(T * N)$이지만, 카운팅 방법이 실제로 더 빠르게 동작할 가능성이 큽니다.
• 이 차이는 매우 미묘할 수 있지만, 수백만 건의 연산이 있을 때는 눈에 띄게 나타날 수 있습니다.
• 따라서, 카운팅 방법이 메모리 사용량이 적고 연산이 간단하여 일반적으로 더 빠르고 효율적일 수 있습니다.

실제 코드 속도를 보더라도 다음과 같이 두 번째가 빠른 것을 확인할 수 있습니다.

스택 결과

예제 입력 2 결과

19.12669801712036

카운팅 결과

예제 입력 2 결과

8.185030937194824

---

마무리

이번 문제에서는 괄호의 짝을 맞추는 방법을 스택을 이용한 방법과 단순한 카운팅 방법으로 해결했습니다. 스택을 이용한 방법은 괄호 짝을 추적하는 데 직관적이며, 카운팅 방법은 메모리 사용량을 줄이는 데 유리합니다. 두 가지 방법 모두 효율적이며 문제의 요구 사항을 충족합니다.

이 문제를 통해 스택과 문자열 처리에 대한 기초적인 개념을 다시 한 번 복습할 수 있었으며, 이러한 문제들은 코딩 테스트에서 자주 출제되므로 익숙해져야 합니다. 끝까지 집중해서 다음 문제들도 차근차근 해결해 나가봅시다!

전체 코드는 저의 깃허브에서 확인하실 수 있습니다.

읽어주셔서 감사합니다!

더 나은 개발자가 될거야!!💪