3986번: 좋은 단어

문제

단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 짝을 지을 때, 선이 교차하지 않고 모든 글자를 짝지을 수 있는 단어를 '좋은 단어'라고 합니다. 주어진 N개의 단어 중 좋은 단어의 개수를 구하는 문제입니다.

• 입력: 첫째 줄에 단어의 수 N (1 ≤ N ≤ 100,000)이 주어집니다. 둘째 줄부터 N개의 줄에 'A'와 'B'로만 이루어진 단어가 한 줄에 하나씩 주어집니다.
• 출력: 첫째 줄에 좋은 단어의 개수를 출력합니다.

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

풀이

선이 교차하지 않고 인접한 같은 글자끼리 짝을 지어 소거해 나가는 조건은 전형적인 괄호 짝맞추기(올바른 괄호 문자열) 문제의 논리와 완전히 동일합니다. 따라서 스택(Stack) 구조를 사용하면 아주 쉽게 해결할 수 있습니다.

1. Deque 활용: 각 단어를 구성하는 문자를 순서대로 확인하며 이전 상태를 기억하기 위해 ArrayDeque를 선언합니다.
2. 글자 짝맞추기:
   • 덱(Deque)이 비어있지 않고, 맨 위 글자(st.peek())와 현재 글자(c)가 서로 같다면 짝이 맞는 것이므로 빼냅니다(pop).
   • 덱이 비어있거나, 맨 위 글자와 현재 글자가 다르다면 짝을 맞출 수 없으므로 현재 글자를 넣습니다(push).
3. 좋은 단어 판별: 단어의 모든 글자를 확인한 후 덱이 완전히 비어있다면(st.isEmpty()), 모든 글자가 교차하지 않고 무사히 짝을 지어 소거되었다는 뜻이므로 정답 카운트를 1 증가시킵니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int ans = 0;
       
       while (n-- > 0) {
          String s = br.readLine();
 
          Deque<Character> dq = new ArrayDeque<>();

          for (char c : s.toCharArray()) {
             // 덱이 비어있지 않고, 맨 위 문자와 현재 문자가 같으면 짝지어 제거
             if (!dq.isEmpty() && dq.peek() == c) {
                dq.poll();
             } else {
                // 다르면 덱에 추가
                dq.push(c);
             }
          }

          // 덱이 비어있다면 모든 글자가 짝을 지어 사라졌다는 의미 (좋은 단어)
          if (dq.isEmpty()) {
             ans++;
          }
       }

       bw.write(ans + "");
       
       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

자료구조 (Data Structure), 스택 (Stack)