- 문제 링크
백준 4949번 - 균형잡힌 세상
해결 전략
본 문제를 풀다가 막힌 사람의 90% 이상은 아마 문자열 입력 때문이었을 것이다. 사실 문제 해결을 위한 Algorithm은 어렵지 않게 떠올릴 수 있다. Stack을 사용해야한다는 것을 말이다. 스택의 'Top에서만 삽입/삭제의 연산이 가능함'이라는 특성을 이용해, Backtrack이 필요한 문제 상황이라면 언제든지 스택을 떠올려야 한다. 그것이 PS 본능이다.
Backtrack이 필요한 상황에서, 만약 자료구조가 선형적이라면, 그것은 높은 확률로 스택으로 가볍게 해결할 수 있는 문제일 것이다. 자료구조가 트리라면 DFS와 연결될 확률이 높을 것이다. 아무튼 각설하고 본 문제는 '선형적'이고, 'Backtrack이 필요'한 문제임을 확인할 수 있으므로 스택으로 문제 해결 아이디어를 어렵지 않게 설계할 수 있을 것이다.
문자열을 쭉 스택에 넣어가는데, )를 만나는 경우 (를 만날 때까지 Pop한다. 그 과정에서 [가 발견되면 no이다.
]을 만나는 경우 마찬가지로 [을 만날 때까지 Pop한다. 그 과정에서 (가 발견되면 no이다.
이 두 아이디어를 기반으로, 몇 가지 예외 상황에 대한 처리를 더해주면 된다.
본 문제의 관건은, 해결 아이디어보다는 사실 '문자열 입력 방법'이라고 생각한다. 본인을 포함해 많은 이들이 컴퓨터공학을 지속적으로 공부하다보면 학습 초반에 배웠던 기초 내용에 조금 무뎌지는 경우가 많다.
특히 첫 언어를 C언어로 학습했던 이들에게 '문자열 포맷팅, 서식 지정자, 플래그'등의 개념은, C 학습 이후의 컴퓨터공학 학습 과정에서 해당 개념을 다룰 일이 많지 않아 많이 무뎌졌을 것이다.
사실, 다른 것은 Naive하게 처리할 수 있으니 상관 없는데, 우리는 한 가지는 반드시 오래 기억해야할 것이 있다.
공백도 문자열로 받아들이고 싶다면, scanf("%[^\n]s", str);을 이용해야 한다.
"%[^문자]s"는, '문자'를 만나기 전까지 문자열을 읽어들인다. '문자'에 복수의 문자를 나열해 여러 문자에 대해서도 처리할 수 있다.
다른 건 몰라도, 이 개념은 오래 기억해야한다. 적어도 PS를 준비하고자 하는 사람이라면 말이다.
본 문제의 포스팅은 여기까지 하겠다. 아래는 코드이다. 참고로, 입력 스트림 버퍼에 남아있는 '\n'를 getchar()로 클리어하고 있는 부분도 주목하자.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
// BOJ - 4949 Balanced World
using namespace std;
stack<char> s;
bool yesOrNo(char *str) {
int i = 0;
if (str[0] == ')' || str[0] == ']') return false;
s.push(str[i++]);
while (str[i]) {
if (str[i] == ')') {
while (!s.empty() && s.top() != '(') {
if (s.top() == '[') return false;
s.pop();
}
if (s.empty()) return false;
if (!s.empty() && s.top() == '(') s.pop();
}
else if (str[i] == ']') {
while (!s.empty() && s.top() != '[') {
if (s.top() == '(') return false;
s.pop();
}
if (s.empty()) return false;
if (!s.empty() && s.top() == '[') s.pop();
}
else s.push(str[i]);
i++;
}
while (!s.empty()) {
if (s.top() == '(' || s.top() == '[') return false;
s.pop();
}
return true;
}
int main(void) {
char str[101];
while (1) {
scanf("%[^\n]s", str); getchar();
if (str[0] == '.' && strlen(str) == 1) break;
if (yesOrNo(str)) cout << "yes\n";
else cout << "no\n";
while (!s.empty()) s.pop();
}
return 0;
}