[알고스팟] 짝이 맞지 않은 괄호(BRACKETS2)

[알고스팟] 짝이 맞지 않은 괄호(BRACKETS2)

목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "짝이 맞지 않는 괄호"를 풀어보자

문제 URL

풀이

"짝이 맞지 않은 괄호" 같은 문제는 스택을 이용하는 대표적인 알고리즘 문제입니다. 이 문제의 경우 다음의 조건을 검사해야 합니다.

1. 모든 괄호는 쌍이 맞아야 한다.
2. 모든 괄호는 먼저 열리고 그 후에 닫혀야 한다.
3. 어떠한 쌍도 교차될 수 없다. (ex : "({)}" )

이 문제 역시 스위핑 알고리즘을 기반으로 짭니다. 문제의 핵심은 닫히는 괄호가 나올때 짝이 맞는 열리는 괄호가 있는가입니다. 알고리즘의 가장 큰 줄기는 다음과 같습니다.

1. 입력 문자열을 다음과 같이 순회합니다.
   1. 현재 문자가 괄호를 여는 문자들 "(", "{", "[" 중 하나라면, 스택에 넣습니다.
   2. 현재 문자가 괄호를 닫는 문자들 ")", "}", "]" 중 하나라면, 아래의 두 조건을 검사합니다. 만약 아래 두 조건을 통과한다면, 스택에서 가장 나중에 저장된 것을 제거합니다.
      1. 스택이 비어있지 않은지 여부
      2. 괄호를 닫는 현재 문자와, 스택에 가장 나중에 저장된 괄호를 여는 문자의 수준이 같은지 여부
2. 순회가 종료한 후에, 스택이 비었다면, 성공한 것이고 아니라면 실패한 것입니다.

예제를 통해서 이 알고리즘이 어떻게 동작하는지 확인하겠습니다. 먼저 문제의 세번째 예제를 보면 입력은 다음과 같습니다.

s = "({}[(){}])"

앞서 말했다시피, 이 문제를 풀기 위해서는 문자를 저장하는 스택이 필요합니다. 따라서 스택을 생성합니다. 그 후, 0부터 s의 크기-1까지 순회하면 됩니다.

index = 0, curr = "("

현재 검사하는 문자 "("는 괄호를 여는 문자이므로 스택에 넣습니다.

st = ["("]

그 후 순회를 진행합니다.

index = 1, curr = "{" 
st = ["(", "{"]

현재 검사하는 문자 "{"는 괄호를 여는 문자이므로 스택에 넣습니다. 이는 위의 동작과 같습니다.

index = 2, curr = "}"

현재 닫히는 문자가 나왔습니다. 이러면 먼저 스택이 비었는지 확인합니다. 만약 비었다면, 열리는 괄호가 없는데 닫힌 괄호가 나온 것이므로 실패해야 합니다. 다행히 현재 스택은 다음과 같이 저장하고 있습니다. 즉 비지 않았다는 뜻이지요.

st = ["(", "{"]

그 후, 스택에 가장 나중에 저장된 열린 괄호와, 현재 닫힌 괄호 "}"와 같은 수준의 괄호인지 확인해야 합니다. 만약 수준이 맞지 않는다면 틀렸다는 실패했다는 뜻입니다. 다행히 현재 스택에서 마지막으로 저장된, 괄호는 "{" 이므로 같은 수준의 괄호입니다. 검사를 마치고 스택에서 그 괄호를 제거합니다.

st = ["("]

이런 식으로 알고리즘을 진행하면, 각 index에 따른 동작은 다음과 같습니다.

index = 3, curr ="[" (여는 괄호이므로 스택에 저장합니다.)
st = ["(", "["]

index = 4, curr = "(" (여는 괄호이므로 스택에 저장합니다.)
st = ["(", "[", "("]

index = 5, curr = ")" (닫힌 괄호이므로 2개의 조건 검사후, 맞다면 스택에서 나중에 저장된 괄호를 제거합니다.)
st = ["(", "["]

index = 6, curr = "{" (여는 괄호이므로 스택에 저장합니다.)
st = ["(", "[", "{"]

index = 7, curr = "}" (닫힌 괄호이므로 2개의 조건 검사후, 맞다면 스택에서 나중에 저장된 괄호를 제거합니다.)
st = ["(", "["]

index = 8, curr = "]" (닫힌 괄호이므로 2개의 조건 검사후, 맞다면 스택에서 나중에 저장된 괄호를 제거합니다.)
st = ["("]

index = 9, curr = ")" (닫힌 괄호이므로 2개의 조건 검사후, 맞다면 스택에서 나중에 저장된 괄호를 제거합니다.)
st = []

순회를 마치고 현재 스택이 비어있으니, 이 문자열은 짝이 맞는 괄호입니다. 이번엔 실패하는 케이스를 살펴봅시다. 두번째 예제 입력은 다음과 같습니다.

s = "({[}])"

자, 여기서는 동작 과정만 살펴보겠습니다. 왜 이렇게 동작하는지 한 번 스스로 점검하는 것도 좋을 것 같습니다.

index = 0, curr = "("
st = ["("]

index = 1, curr = "{"
st = ["(", "{"]

index = 2, curr = "["
st = ["(", "{", "["]

index = 3, curr = "}" 
실패

index = 3일 때 현재 검사 문자는 닫히는 괄호 "}"입니다. 현재 스택에 가장 나중에 저장된 열린 괄호 "["와 수준이 맞지 않으므로 이 테스트는 실패해야 합니다. 이 문제를 풀기 위해서는 c++ 표준 라이브러리 string 클래스에서 제공하는 find를 이용하면 보다 간결하게 표현할 수 있습니다. 괄호의 수준을 검사하는 동작을 O(1)에 가깝게 만들 수 있으므로, 이 알고리즘의 시간 복잡도는 O(N)이라고 볼 수 있습니다. 다음은 코드입니다.

코드

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

using namespace std;

bool solution(const string& s) {
	const string opened = "({["; //열리는 괄호 수준 ( : 0, { : 1, [ : 2
	const string closed = ")}]"; //닫히는 괄호 수준 ) : 0, } : 1, ] : 2
	stack<char> st;              //스택 생성

	for (const auto &c : s) {
		//string.find(character)는 문자를 찾으면 index를 아니라면 -1을 반환
                //열린 괄호라면 따지지 않고 스택 저장.
		if (opened.find(c) != -1) {
			st.push(c);
		}
		else {
                //닫힌 괄호라면, 먼저 스택이 빈지 검사
			if (st.empty()) {
				return false;
			}
                //그후, 현재 닫힌 괄호와, 스택에 가장 나중에 저장된 열린 괄호의 수준을 검사
			if (opened.find(st.top()) != closed.find(c)) {
				return false;
			}
                //두 조건을 만족한다면, 스택에서 열린 괄호 제거
			st.pop();
		}
		
	}
        //스택이 비었다면 성공, 아니라면 실패
	return st.empty();
}

int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		string s;
		cin >> s;

		if (solution(s)) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}

	return 0;
}