문제
A와 B로만 이루어진 단어에서 같은 글자끼리 아치형으로 짝지을 수 있으면 "좋은 단어"이다. N개의 단어 중 좋은 단어의 수를 구하라.
입력
첫째 줄에 N, 이후 N개의 단어가 주어진다.
출력
좋은 단어의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 ABAB AABB ABBA | 2 |
풀이
스택으로 같은 문자가 연속하면 제거하여, 모두 제거되면 좋은 단어이다.
- 홀수 길이 단어는 짝지을 수 없으므로 건너뛴다
- 각 문자를 순서대로 스택에 넣되, 스택 맨 위와 같은 문자면 꺼낸다 (짝 제거)
- 모든 문자 처리 후 스택이 비어있으면 좋은 단어이다
- 좋은 단어의 수를 출력한다
핵심 아이디어: 괄호 매칭과 같은 원리이다. 같은 문자가 인접하면 제거하고, 최종적으로 모두 제거되면 아치형 짝짓기가 가능하다.
코드
package day399;
import java.util.*;
import java.io.*;
public class Day350BOJ3986좋은단어 {
static int N, ans = 0;
static Stack<Character> stack;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
String s = br.readLine();
if (s.length() % 2 == 1)
continue;
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())
ans++;
}
System.out.print(ans);
}
}복잡도
- 시간: O(N)
- 공간: O(N)