[BOJ] 3986번 : 좋은 단어

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

3986번: 좋은 단어

 

 

문제 파악

아래 예시처럼 같은 단어끼리이었을 경우 선이 겹친다면 안 좋은 단어, 겹치지 않는다면 좋은 단어로 판단했다.

 

 

다음과 같이 아치형으로 같은 문자 끼리 이었을 경우 겹치지 않는다면 좋은 단어

다음과 같이 아치형으로 같은 문자 끼리 이었을 경우 겹친다면 안좋은 단어

 

그리고 분류를 보아하니 스택이 적혀 있어서 스택을 활용하여 문제를 해결하였다.

 

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 IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int answer = 0;

        for(int idx = 0; idx<N;idx++) {
            String input = br.readLine();
            answer+= GoodWord(input);
        }
        System.out.println(answer);
        br.close();
    }

    private static int GoodWord(String input) {
        Stack<Character> st = new Stack<>();

        for(int idx = 0; idx<input.length();idx++) {
            char ch = input.charAt(idx);
            if(!st.isEmpty() && st.peek().equals(ch)) {
                st.pop();
            }
            else{
                st.push(input.charAt(idx));
            }
        }
        return st.isEmpty() ? 1: 0;
    }
}

 

과연 알고리즘 분류에 스택이라고 적혀 있지 않았으면 내가 풀 수 있었을까..