오늘 문제는 스택 자료 구조 유형의 문제에서 기본?이 되는 괄호 문제입니다.
오늘도 집중해봅시다!
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번
알고리즘 분류
3. 나의 풀이
문제 이해 및 접근
이번 문제는 괄호 문자열이 올바른 괄호 문자열(VPS, Valid Parenthesis String)인지 판단하는 문제입니다. 주어진 문자열이 올바른 VPS인지 판단하기 위해서는 괄호의 열림과 닫힘이 올바르게 짝지어져야 합니다.
이 문제를 해결하기 위해 두 가지 접근 방식을 사용했습니다:
- 스택(Stack)을 활용한 방법: 괄호가 올바르게 짝지어졌는지를 스택을 이용해 확인합니다.
- 카운팅(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번 수행되므로, 각 테스트 케이스에 대한 시간 복잡도는 입니다.
전체적으로 T개의 테스트 케이스에 대해 이 작업이 반복되므로, 전체 시간 복잡도는 입니다.
두 번째 풀이: 카운팅을 이용한 방법
이 방법에서는 스택 대신 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) 시간 복잡도를 가집니다.
따라서, 각 테스트 케이스에 대한 시간 복잡도는 입니다.
전체적으로 T개의 테스트 케이스에 대해 이 작업이 반복되므로, 전체 시간 복잡도는 입니다.
하지만! 실질적인 속도는 카운팅을 이용한 방법이 더 빠를것입니다.
그 이유는 다음과 같습니다:
1. 메모리 접근과 관리:
- 카운팅 방법: 이 방법에서는 단순히 정수 하나(
total)를 사용하여 카운팅합니다. 이 변수는 CPU 캐시에서 관리될 수 있기 때문에 접근 속도가 매우 빠릅니다. - 스택 방법: 이 방법에서는 리스트를 사용하여 스택을 구현합니다. 리스트의 크기가 커지면 메모리 관리 비용이 증가할 수 있으며, 스택에서
append와pop연산이 자주 일어나게 됩니다. 이러한 연산들은 개별적으로는 O(1)이지만, 메모리 할당이나 리스트 크기 증가에 따라 약간의 오버헤드가 발생할 수 있습니다.
2. 연산 간소화:
- 카운팅 방법: 단순히
total변수에 더하고 빼는 연산만을 수행하므로, 연산 자체가 매우 간단합니다. - 스택 방법: 스택의 경우,
append와pop연산이 필요하며, 스택의 상태를 계속 관리해야 합니다. 비록 각 연산이 O(1)이라 하더라도, 실제 실행 시의 오버헤드는 카운팅 방법보다 클 수 있습니다.
3. 조건문 처리:
- 카운팅 방법:
total값이 음수가 되는 순간 바로NO를 출력하고 반복을 종료할 수 있습니다. 이 경우, 루프를 조기에 종료하여 불필요한 연산을 줄일 수 있습니다. - 스택 방법: 스택을 이용할 때도 중간에 조기 종료가 가능하지만, 스택의 크기를 체크하고 pop할 때 발생하는 추가 연산이 필요합니다.
결론:
- 이론적인 시간 복잡도는 동일하게 이지만, 카운팅 방법이 실제로 더 빠르게 동작할 가능성이 큽니다.
- 이 차이는 매우 미묘할 수 있지만, 수백만 건의 연산이 있을 때는 눈에 띄게 나타날 수 있습니다.
- 따라서, 카운팅 방법이 메모리 사용량이 적고 연산이 간단하여 일반적으로 더 빠르고 효율적일 수 있습니다.
실제 코드 속도를 보더라도 다음과 같이 두 번째가 빠른 것을 확인할 수 있습니다.
스택 결과
예제 입력 2 결과
19.12669801712036카운팅 결과
예제 입력 2 결과
8.185030937194824마무리
이번 문제에서는 괄호의 짝을 맞추는 방법을 스택을 이용한 방법과 단순한 카운팅 방법으로 해결했습니다. 스택을 이용한 방법은 괄호 짝을 추적하는 데 직관적이며, 카운팅 방법은 메모리 사용량을 줄이는 데 유리합니다. 두 가지 방법 모두 효율적이며 문제의 요구 사항을 충족합니다.
이 문제를 통해 스택과 문자열 처리에 대한 기초적인 개념을 다시 한 번 복습할 수 있었으며, 이러한 문제들은 코딩 테스트에서 자주 출제되므로 익숙해져야 합니다. 끝까지 집중해서 다음 문제들도 차근차근 해결해 나가봅시다!
전체 코드는 저의 깃허브에서 확인하실 수 있습니다.
읽어주셔서 감사합니다!
더 나은 개발자가 될거야!!💪
