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

문제 링크

---

1. 아이디어

단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 짓는 것이 괄호의 쌍을 맞추는 것과 동일하다. 스택 자료구조를 활용해서 괄호 쌍 맞추기를 하듯이 해주면 된다.

---

2. 코드

1. 풀이 [Java]

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);
    }
}

2. 풀이 [C++]

#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;
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---