알고리즘 문제해결 전략 Chapter 19 - BRACKETS2(C++)

포타토·2019년 12월 30일
0

알고리즘

목록 보기
12/76

예제: 짝이 맞지 않는 괄호

문제
Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas have problems: some of the brackets are mismatched! Since there are so many formulas in his paper, he decided to check their validity with a computer program.

The following kinds of brackets are included in Best White’s paper.

  • Round brackets are opened by a ( and closed by a ).
  • Curly brackets are opened by a { and closed by a }.
  • Square brackets are opened by a [ and closed by a ].

A formula is said well-matched when the following conditions are met:

  1. Every bracket has a corresponding pair. ( corresponds to ), [ corresponds to ], et cetera.
  2. Every bracket pair is opened first, and closed later.
  3. No two pairs "cross" each other. For example, [(]) is not well-matched.

Write a program to help Best White by checking if each of his formulas is well-matched. To make the problem easier, everything other than brackets are removed from the formulas.

입력
The first line of the input will contain the number of test cases C (1≤C≤100). Each test is given in a single line as a character string. The strings will only include characters in "{}" (quotes for clarity). The length of the string will not exceed 10,000.

출력
For each test case, print a single line "YES" when the formula is well-matched; print "NO" otherwise. (quotes for clarity)

예제 입력

3
()()
({[}])
({}[(){}])

예제 출력

YES
NO
YES

풀이

와 무슨 영어냐.. 하겠지만, 사실 stack 예제로 심심치 않게 보았던 괄호 맞추기 문제이다.
예제만 봐도 알 것이다.

라고 말은 했지만, 필자도 오랜만에 풀어서 그런지 예외처리를 하나 하지 않아 잠시 애를 먹었다.

로직은 여는 괄호 ({[ 일 때는 stack에 넣어주고, 닫는 괄호 )}] 일 때에 하나씩 스택에서 꺼내어 비교해서 짝이 맞지 않을 경우 실패이다. 짝이 맞는다면, pop을 해준다.
최종적으로 스택의 사이즈가 0이면 true이다.

예외는 로직에 따라 다르겠지만, 필자의 경우에 아래와 같은 예외를 처리하였다.
1. 문자가 닫는 기호로 시작할 경우 무조건 false
2. stack에서 top()을 하기 전에, stack이 비어있으면 무조건 false

전체적인 소스코드는 아래와 같다.

소스 코드

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

using namespace std;

bool brackets(const string& word) {
	if (word[0] == ')' || word[0] == '}' || word[0] == ']') return false;
	stack<char> st;

	for (int i = 0; i < word.size(); i++) {
		if (word[i] == '(' || word[i] == '{' || word[i] == '[') {
			st.push(word[i]);
		}
		else {
			if (st.size() == 0) return false;
			if (st.top() == '(' && word[i] == ')') st.pop();
			else if (st.top() == '{' && word[i] == '}') st.pop();
			else if (st.top() == '[' && word[i] == ']') st.pop();
			else return false;
		}
	}

	return st.size() == 0;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		string word;
		cin >> word;

		cout << (brackets(word) ? "YES" : "NO") << endl;
	}

	return 0;
}

풀이 후기

정말.. 예외처리는 아무리 강조해도 너무나 중요한듯 하다.
algospot은 leetcode와 달리 틀린 테스트케이스도 알려주지 않기 때문에 더 어렵게 느껴진다.

그리고, 풀이에서는 string의 find 함수를 사용하여 깔끔하게 풀었던데, 필자의 풀이보다는 조금 더 느린걸 보아 find 함수가 느리긴 한가보다.

아무튼, 예외처리 확실히 하자!

profile
개발자 성장일기

0개의 댓글