[백준] 3986번. 좋은 단어

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

---

문제

---

풀이

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 t = Integer.parseInt(br.readLine());
        int count = 0;
        
        for (int i = 0; i < t; i++) {
            String s = br.readLine();
            if (s.length() % 2 == 1) {
                continue;
            }
            Stack<Character> stack = new Stack<>();
            stack.push(s.charAt(0));
            
            for (int j = 1; j < s.length(); j++) {
                if (stack.size() > 0 && stack.peek() == s.charAt(j)) {
                    stack.pop();
                } else {
                    stack.push(s.charAt(j));
                }
            }
            if (stack.isEmpty()) count++;
        }
        System.out.print(count);
    }

}

 

먼저 좋은 문자열이 된다는 기준을 잘 잡아야 한다. ABBA 같이 A와 A가 연결되며 그 사이에 B와 B가 연결된다. 이러면 좋은 단어가 된다.

반대로, ABAB와 같이 두 선이 교차하는 경우는 좋은 단어가 아니다.

 

결과적으로 문자열의 길이가 짝수가 되는 것이 우선이다. 문자열의 길이가 짝수가 되지 못한다면 이는 좋은 단어일 가능성이 없다.

 

문자열의 현재 위치와 스택의 끝을 비교하며 문자가 같을 경우 삭제시켜 주고, 이후 스택이 비어있는지 검사를 통해 좋은 단어의 개수를 카운트한다.