<Algorithm> 80. 3986번 좋은 단어

1. 3986번 좋은 단어

• Stack 기본문제, 문제를 이해하지 못해서 상당히 시간이 걸렸다. 처음에 단순히 영역 구하는 문제인 줄 알고 DFS로 접근했다.

• 번외로 테스트케이스가 하나밖에 없어서 몰랐는데 단어길이가 제 각각이었고 그러다 보니 Array 예외가 자꾸 발생했다.

• 제각각인 라인을 잡을때는 배열과 Input을 따로 두는 것이 좋을 것 같다.

• 본론으로 돌아와서 이 문제는 문자열이 주어지고 문자를 지워나가는 문제이다. ABBA -> BB를 지우고 AA를 지운다 

• 이 표현을 단어위로 묶은다는 표현을 해서 이해가 안됬던 것 같다. 알고리즘에서 기본적으로 문제 이해 가장 중요한 것 같다.

• Stack을 이용해서 넣고 지우고를 반복해서 비어있으면 좋은단어 아니면 아닌단어로 풀이하였다.

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 {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int count = 0;
        for(int i = 0; i < N ; i++) {
            Stack<Character> stack = new Stack<>(); 
            String str = br.readLine();
            for(int j = 0; j < str.length();j++) {
                if(!stack.isEmpty() && stack.peek() == str.charAt(j)) {
                    // AA 이거나 BB 일경우  좋은 단어가 되기 때문에 stack에서 빼준다.
                    stack.pop();
                }else {
                    // AB 일때와 첫 시작 단어는 stack에 넣어준다.
                    stack.push(str.charAt(j));
                }
            }
            if(stack.isEmpty()) {
                count++;
                // stack이 비어있다는 것은 모든 단어가 지워진것 이기 때문에 좋은단어를 카운트 해준다.
            }
        }
        System.out.println(count);
    }
}
 

참고 & 출처