[BOJ 25001 // C++] Pen

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25001번 문제인 Pen이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25001 

25001번: Pen

주어진 문자열의 앞뒤에 적절히 괄호를 붙여 이 문자열을 올바른 괄호문자열로 만들 수 있는지를 판별하는 문제이다.

 

문자열의 앞쪽으로 ')' 등의 닫는 괄호를 추가한다면 해당 괄호를 닫기 위한 추가적인 여는 괄호가 필요해지므로 앞쪽에는 여는 괄호만을 추가해야 한다. 마찬가지로, 문자열의 뒤쪽에는 닫는 괄호만을 추가해야 한다.

 

잘 알려진, 스택을 이용한 괄호문자열 판별 방식으로 주어진 괄호열을 처리하되, 닫는 괄호의 경우 바로 앞의 문자가 여는 괄호열이 아닌 경우 계속 쌓아나가면, 중간에 잘못된 쌍으로 이루어진 "여는 괄호로 시작해 닫는 괄호로 끝난 올바르지 못한 부분문자열"이 존재하는 걸 감지하거나 처음에는 닫는 괄호만이 이어지고 뒤에는 여는 괄호만이 이어지는 괄호열을 얻게 된다.

 

중간에 "여는 괄호로 시작해 닫는 괄호로 끝난 올바르지 못한 부분문자열"을 찾은 경우 NIE를 출력하고, 그렇지 않다면 마지막으로 얻은 괄호열이 올바른 괄호문자열이 되게끔 하는 괄호열을 앞뒤에 붙여 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s, sleft = "", sright = "";
string tmp = "";

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	for (auto l : s) {
		if (l == ')') {
			if (tmp.empty()) {
				tmp.push_back(l);
			}
			else if (tmp.back() == '{' || tmp.back() == '[') {
				cout << "NIE";
				return 0;
			}
			else if (tmp.back() == '(') tmp.pop_back();
			else tmp.push_back(l);
		}
		else if (l == '}') {
			if (tmp.empty()) {
				tmp.push_back(l);
			}
			else if (tmp.back() == '(' || tmp.back() == '[') {
				cout << "NIE";
				return 0;
			}
			else if (tmp.back() == '{') tmp.pop_back();
			else tmp.push_back(l);
		}
		else if (l == ']') {
			if (tmp.empty()) {
				tmp.push_back(l);
			}
			else if (tmp.back() == '(' || tmp.back() == '{') {
				cout << "NIE";
				return 0;
			}
			else if (tmp.back() == '[') tmp.pop_back();
			else tmp.push_back(l);
		}
		else tmp.push_back(l);
	}

	for (auto l : tmp) {
		if (l == ')') sleft += '(';
		else if (l == '}') sleft += '{';
		else if (l == ']') sleft += '[';
		else if (l == '(') sright += ')';
		else if (l == '{') sright += '}';
		else sright += ']';
	}

	reverse(sleft.begin(), sleft.end());
	reverse(sright.begin(), sright.end());

	cout << sleft << s << sright;
}