[백준 3986번] 파이썬 - 좋은 단어

백준 3986 - 좋은 단어

시간 제한 1초, 메모리 제한 256MB

# 조건

• 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다.
• 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다.
• 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다!
• 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.
• 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다.
• 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다.
• 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

• 첫째 줄에 단어의 수 N이 주어진다.(1<=N<=100)
• 다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다.
• 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

• 첫째 줄에 좋은 단어의 수를 출력한다.

# 접근 방법

• 아치형 곡선을 그려 선끼리 교차하지 않는 다는 것이 어떤 의미인지 이해하는 것이 어려웠다.
• 곡선의 높낮이는 상관 없이 서로 겹치치만 않으면 된다고 생각하였고 이 말을 풀어서 생각하니 A와 B를 쌍을 지을 때, 서로 교차되어 있지 않는다라고 이해하였다
  • 즉, ABAB의 경우 쌍을 지을 때 교차되지만 ABBA의 경우 B를 잇는 아치 위로 A를 잇는 아치를 그릴 수 있으므로 조건에 위배되지 않는다.
• 따라서, 스택을 이용하여 풀어준다.
• TARGET word를 1개씩 pop 하면서 temp의 top이 현재 pop한 단어와 같다면 temp에서 pop, 아니라면 push를 해준다.
• 마지막에 temp가 남아있다면 좋은 단어가 아니다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
result = 0
for _ in range(N):
    target = list(input().strip())
    temp = []
    while target:
        now = target.pop()
        if temp and temp[-1] == now:
            temp.pop()
        else:
            temp.append(now)

    if not temp:
        result += 1

print(result)

 

• 아래는 Cpp

#include <iostream>
#include <stack>
using namespace std;

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

    int result = 0;
    while (N--) {
        stack<char> stk;
        string word;
        cin >> word;

        for (int i = 0; i < word.length(); i++) {
            if (stk.empty()) {
                stk.push(word[i]);
            }
            else {
                if (stk.top() == word[i]) {
                    stk.pop();
                }
                else {
                    stk.push(word[i]);
                }
            }
        }
        if (stk.empty()) {
            result++;
        }
    }

    cout << result;

    return 0;
}