[백준] 3986. 좋은 단어(Java)

문제

3986번: 좋은 단어

풀이

문제에 나온 '좋은 단어'가 되기 위해서는 같은 문자를 짝짓는 선을 그엇을 때, 교차하는 선이 없어야 한다.

'AABB'와 같이 같은 문자끼리 붙어있거나, 'ABBA'처럼 떨어져 있어도 선이 교차하지 않아야 한다.

 

이러한 문제에서 stack 자료구조를 사용한다면 쉽게 풀 수 있다.

 

주어진 String을 순회하면서

1) stack이 비어있다면 -> 현재 값 push

2) stack이 비어있지 않았을 때, stack의 최상단 값 == 현재 값이라면 -> stack의 최상단 값 제거(pop)

3) stack이 비어있지 않았을 때, stack의 최상단 값 != 현재 값이라면 ->  현재 값 push
    순회를 마치고나서 stack이 비어있다면 '좋은 단어'이므로 ans ++

코드

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

        Stack<Character> stack;

        for(int i = 0 ; i < N ; i ++){
            stack = new Stack<>();

            String s = br.readLine();
            int len = s.length();

            stack.push(s.charAt(0));

            for(int j = 1 ; j < len ; j ++){
                char cur = s.charAt(j);
                char peek;

                // 스택이 비어있다면 push
                if(stack.size() == 0) stack.push(cur);

                // 비어있지 않다면
                else{
                    peek = stack.peek();

                    if(peek == cur) stack.pop();
                    else stack.push(cur);
                }
            }

            if(stack.size() == 0) ans ++;
        }

        System.out.print(ans);
    }
}