[알고리즘] 백준 3986번 - 좋은 단어

문제

입력과 출력

우선 문제는 다음과 같은데,, 사실 처음 보는 유형의 문제라(아직 알린이라 그런듯함,,) 이해하는 시간도 꽤 오래 걸렸던 것 같다.

A 또는 B가 포함된 입력 문자열이 주어지고 단어 위로 아치형 곡선을 그어 각 글자를 정확히 다른 위치에 있는 같은 글자와 짝을 지었는데 이때 곡선들이 교차하지 않는 것이 좋은 단어가 될 수 있는 조건이다.

그림으로 설명하자면 아래와 같다.

예제 입력 1의 출력값이 2인 이유

첫 접근은 A와 B의 위치 관계에서 규칙을 얻으려고 접근했던 것 같다. 뭔가 순서에 규칙성이 있을 것 같았기 때문이었다. 하지만 규칙을 찾으려고 하면 할수록 계속 나오는 반례에 가로막히고 말았다.

그러던 와중에 문제의 워딩에서 짝을 짓는다는 표현이 눈에 밟혔다. 그와 동시에 보통 이런 문자열이 나오면 길게 늘려보거나 세워보는 등 다양한 관점으로 바라보는 것이 중요하다고 강의에서 배운 점이 떠올랐다.

그래서 세웠다.

문자열을 세워보니 stack의 모습과 비슷해보였다. 이제 규칙성을 생각해보았는데 기존에 문자열이 누워 있을 때는 A나 B의 위치가 서로에게 영향을 주는 것을 위주로 생각을 했었다. A가 이미 있을 때, 다음에 올 수 있는 문자는 A이거나 A앞에 B가 없을 경우 B가 올 수 있다는 느낌으로 생각했었는데 stack으로 관점을 바꾸니 훨씬 쉬워졌다.

stack에 문자열을 앞에서부터 하나씩 삽입하면서 그 전에 삽입했던 문자와 같은 문자면 stack의 top에 있는 문자를 빼내고 다르면 계속 stack에 쌓는다. 모든 문자열의 삽입이 끝난 후 stack이 비어있으면 그 단어는 좋은 단어가 되는 것이다.

아래는 위 로직을 구현한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int N;
int sum = 0;
int greatWord(string word) {
  stack<char> stk;

  for (auto it : word) {
    if (!stk.size()) {
      stk.push(it);
    } else {
      if (stk.top() == it) {
        stk.pop();
      } else {
        stk.push(it);
      }
    }
  }

  if (!stk.size()) {
    return 1;
  } else {
    return 0;
  }
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    string str;
    cin >> str;
    sum += greatWord(str);
  }
  cout << sum;
  return 0;
}

greatWord 라는 함수를 선언하여 구현해보았다. 맨 처음으로 단어가 들어가거나 바로 이전 단계에서 다른 단어와 짝지어지는둥, stack이 비어있을 때 stack의 top()에 접근하려고 하면 에러가 날 수 있으니 비어있는 경우에는 무조건 push()할 수 있도록 해주었다.

솔직히 이런 글을 쓸 때마다 내가 했던 고민의 흔적들, 생각의 흐름 등을 정리하는 것이 굉장히 어렵다고 느껴진다. 분명 생각할 때는 어떠한 근거에 이끌려 차츰 차츰 문제가 원하는 로직에 접근했다고 생각하는데 이렇게 정리하고 보면 그냥 때려 맞춘 것 같다는 느낌이 든다. 이러한 부분을 좀 더 보완해야겠다는 생각이 든다.