[BOJ] 3986 - 좋은 단어

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/3986

3986번: 좋은 단어

난이도: 실버 4

사용언어: JAVA

 

풀이

이 문제는 스택을 이용하는 전형적인 문제입니다. 다른 고려사항도 없어 쉽게 해결할 수 있습니다. 

 

문자열에서 문자를 받아서

 

1. 스택이 비었으면 스택에 push 한다.

2. 스택이 비어있지 않다면, 스택의 top에 있는 문자를 확인한다.

3. 만약 top에 있는 문자와 자신이 같다면, 해당 문자를 스택에서 pop 해준다.

4. 만약 top에 있는 문자와 자신이 같지 않다면, 자신을 스택에 push 해준다.

 

문자열이 끝날 때까지 위의 과정을 반복한 뒤, 문자열이 종료되었을 때 스택이 비어있다면 '좋은 단어'이고, 스택에 문자가 하나라도 들어있다면, '좋은 단어'가 아닙니다.

 

import java.io.*;
import java.util.Stack;
 
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));
        Stack<Character> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());
        int i, j;
        int cnt = 0;
        String s;
        char ch;
        for (i = 0; i < N; i++) {
            s = br.readLine(); // 입력에서 한 줄을 받아서
            for (j = 0; j < s.length(); j++) { // 한 줄이 끝날 때 까지
                ch = s.charAt(j); // 문자 하나씩 받아서
                if (stack.empty()) // 스택이 비었으면?
                   stack.push(ch); // push
                else if (ch == stack.peek()) // 스택의 top에 있는 문자가 자신과 같으면
                   stack.pop(); // pop
                else
                   stack.push(ch); // 스택의 top에 있는 문자가 자신과 다르면 push
            }
            cnt += stack.empty() ? 1 : 0; // 한 줄에 대한 연산이 완료된 후, 스택이 비었으면 좋은 단어.
           stack.clear(); // 스택을 비워줌
        }
        bw.write(String.valueOf(cnt) + "\n"); // 좋은 단어의 총 갯수 출력
        bw.flush();
    }
}