[백준] 3986: 좋은 단어

 

 

첫 줄에 입력 횟수가 주어진다.

그 다음에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 입력한다.

 

이 문제는 스택으로 풀 수 있다.

A와 B가 교차하기만 하는 단어는 좋은 단어가 아니므로 

좋은 단어일 경우에 stack의 size가 0이 되도록 생각해 보면 된다.

 

A와 B가 교차하기만 하는 단어는

A와 B가 계속 번갈아서 입력되므로 

stack.peek()이 입력된 문자와 동일하지 않을 것이고

이 경우에 push()를 한다.

 

교차되지 않는 경우에는 pop()을 하기 때문에 A와 B의 개수가 동일하다면

연산 후의 스택의 사이즈는 0일 것이다.

한 단어가 좋은 단어인지 검사를 한 후에 좋은 단어라면 count를 증가시킨다.

 

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        // StringBuilder를 사용하여 결과를 한 번에 출력하기 위한 객체 생성
        StringBuilder sb = new StringBuilder();

        // BufferedReader를 사용하여 입력을 받기 위한 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 저장할 스택 생성
        Stack<Character> stack = new Stack<>();

        // 입력 횟수
        int T = Integer.parseInt(br.readLine());

        int count = 0;

        // 입력된 횟수만큼 반복
        for (int i = 0; i < T; i++) {
            // 단어 입력
            String s = br.readLine();

            // 단어의 각 문자를 확인
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);

                // 스택이 비어있지 않고 현재 문자가 스택의 맨 위에 있는 문자와 같다면
                if ((!stack.isEmpty()) && c == stack.peek()) {
                    // 스택에서 맨 위의 문자를 제거
                    stack.pop();
                } else {
                    // 스택에 현재 문자를 추가
                    stack.push(c);
                }
            }

            // 스택이 비어있다면 모든 인접한 동일한 문자가 제거된 것이므로 count를 증가
            if (stack.isEmpty()) {
                count++;
            }

            // 스택 비우기
            stack.clear();
        }

        // 결과 출력
        sb.append(count).append("\n");
        System.out.println(sb);
    }
}