3986번 문제 링크

이번 문제는 Stack 구조만 안다면 쉽게 풀 수 있었던 문제였다.

"선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 좋은 단어 이다" 라는 말이 문제의 핵심이었다.

문제 핵심 정리
1. 짝을 지어야 하므로, 문자의 길이는 짝수 이어야 한다.
2. A B A 형태로 선이 겹치는 경우만 아니면, 모두 '좋은 단어' 이다.

😀 정답

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

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;

        while(N-- > 0){
            String str = br.readLine();

            if(str.length()%2 != 0) continue;

            Stack<Character> stack = new Stack<>();
            stack.push(str.charAt(0));
            
            for(int i=1; i < str.length(); i++){
                char ch = str.charAt(i);
                if(!stack.empty() && stack.peek() == ch){
                    stack.pop();
                }else{
                    stack.push(ch);
                }
            }
            if(stack.isEmpty()) count++;
        }
        
        br.close();
        System.out.println(count);
    }
}