[스택] 백준 3986번 좋은단어- Java

https://www.acmicpc.net/problem/3986

✅ 문제

📌  접근방법

처음에 문제를 한 번에 이해를 못했지만, 알고리즘 분류에 스택이라는 힌트를 보고 다시 생각해보니 어떻게 접근할 지 이해가 되었다.

ABAB는 선이 교차해서 좋은 단어가 될 수 없다. ABBA와 AABB는 선끼리 교차하지 않고, 각 글자가 다른 위치에 있는 같은 글자와 짝 지을 수 있어 좋은 단어가 될 수 있다.

스택을 만들어 스택이 비어있는 상태가 되면 좋은 단어가 된다.

🔑 풀이

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 count = 0;

        for (int t = 0; t < N; t++) {
            Stack<Character> st = new Stack<>();
            char[] text = br.readLine().toCharArray();
            st.push(text[0]); // 맨 앞에꺼 먼저 스택에 넣기

            for (int i = 1; i < text.length; i++) {
                char now = text[i];
                if(!st.empty() && st.peek().equals(now)) { // 스택이 비어있지 않고, 스택의 맨 위거와 now랑 같은 경우
                    st.pop();
                } else { // 스택이 비어있거나, 스택의 맨 위거와 now가 서로 다른 경우
                    st.add(now);
                }
            }
            if(st.empty()) { // 스택이 비어있는 경우, 좋은 단어!
                count++;
            }
        }
        System.out.println(count); // 좋은 단어 수 출력

    }
}

 

실행 코드

http://boj.kr/44611131b8f0402aafcafc8c18fb1323