[BaekJoon] #3986 - 좋은 단어 [Java][C++]

문제 링크

---

1. 아이디어

단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 짓는 것이 괄호의 쌍을 맞추는 것과 동일하다. 다만 괄호와 달리 같은 글자가 여는 쪽도 닫는 쪽도 될 수 있으므로, 스택 자료구조를 활용해서 현재 글자가 스택의 맨 위와 같으면 바로 쌍을 지어 꺼내고 다르면 스택에 넣으면 된다. 맨 위와 같은 글자를 바로 짝지어도 되는 이유는, 맨 위 글자와 현재 글자가 나중에 다른 같은 글자들과 짝이 되는 경우라도 곡선이 겹치지 않으려면 한쪽이 다른 쪽을 감싸는 모양이 되는데, 이때 맨 위와 현재를 먼저 짝지어도 나머지가 모두 같은 글자라 결과가 같기 때문이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(L)$

($N$ = 모든 단어 길이의 총합, $L$ = 단어 길이의 최댓값)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        while (n-- > 0) {
            Deque<Character> stack = new ArrayDeque<>();

            String s = br.readLine();
            for (char c : s.toCharArray()) {
                if (stack.isEmpty()) {
                    stack.push(c);
                } else {
                    if (stack.peek() == c) {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                }
            }

            if (stack.isEmpty()) cnt++;
        }

        System.out.println(cnt);
    }
}

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

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

    int n;
    cin >> n;
    int cnt = 0;

    while (n--) {
        stack<char> st;

        string s;
        cin >> s;

        for (char c : s) {
            if (st.empty()) {
                st.push(c);
            } else {
                if (st.top() == c) {
                    st.pop();
                } else {
                    st.push(c);
                }
            }
        }

        if (st.empty()) cnt++;
    }

    cout << cnt;
}

---