이 문제에서는 하나의 표현식(expression)이 주어지며, 우리는 이 표현식의 괄호 번호 시퀀스를 출력해야 합니다. 여는 괄호와 그에 대응하는 닫는 괄호에는 동일한 번호가 부여되며, 괄호가 나타난 순서대로 번호를 매기게 됩니다. 예제를 통해 문제를 더 자세히 살펴보겠습니다.
예시:
입력 : ((()())()) 출력 : 1233442551
설명 − 위 표현식에는 총 5개의 괄호 쌍이 존재하며, 각 괄호가 등장한 순서대로 번호를 부여하여 출력했습니다. 첫 번째 여는 괄호와 마지막 닫는 괄호가 한 쌍을 이루어 같은 번호 '1'을 갖는 식입니다.
문제를 이해했으니, 이제 해결 방법을 만들어 보겠습니다.
문제 해결 접근 방법
이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 여는 괄호의 개수를 세는 변수(leftBracket) 하나를 사용합니다.
- 여는 괄호를 만나면 현재 번호를 출력하고 스택에 push한 뒤, 번호를 1 증가시킵니다.
- 닫는 괄호를 만나면 스택의 top에 있는 번호를 출력하고 pop합니다. 이 번호가 바로 짝이 되는 여는 괄호의 번호입니다.
알고리즘
1단계 : leftBracket = 1로 초기화하고, 빈 스택 rightBracket을 생성한다.
2단계 : 변수 i = 0부터 n-1까지 표현식을 순회한다.
3단계 : expression[i] == '(' 즉, 여는 괄호를 만나면,
3.1단계 : leftBracket 값을 출력한다.
3.2단계 : leftBracket 값을 스택에 push한다.
3.3단계 : leftBracket을 1 증가시킨다.
4단계 : expression[i] == ')' 즉, 닫는 괄호를 만나면,
4.1단계 : 스택의 top 값을 출력한다.
4.2단계 : 스택의 top 요소를 pop한다.
5단계 : 종료한다.
구현 예제
이제 위 알고리즘의 실제 구현을 보여주는 C++ 프로그램을 작성해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void bracketCount(string expression, int n){
int leftBracket = 1;
stack<int> rightBracket;
for (int i = 0; i < n; i++) {
if (expression[i] == '(') {
cout<<leftBracket<<" ";
rightBracket.push(leftBracket);
leftBracket++;
}
else if(expression[i] == ')') {
cout<<rightBracket.top() << " ";
rightBracket.pop();
}
}
}
int main(){
string expression = "()((())()())";
int n = expression.size();
bracketCount(expression, n);
return 0;
}
출력
1 1 2 3 4 4 3 5 5 6 6 2
입력 표현식 ()((())()())에는 총 6개의 괄호 쌍이 있으며, 각 위치의 괄호가 속한 쌍의 번호가 순서대로 출력됩니다. 예를 들어 맨 앞의 ()는 1번 쌍이므로 '1 1'이 먼저 출력됩니다.
복잡도 분석
- 시간 복잡도: O(n) − 표현식을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(n) − 최악의 경우 모든 여는 괄호가 스택에 저장될 수 있습니다.