[Java] BOJ3986 - 좋은 단어

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

 

3986번: 좋은 단어

 

 

💬 예제 설명

예제 입력 1의 경우를 예시로 들어보자.

첫째 줄에 단어의 수 N이 주어지고, 다음 N개 줄에 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다.

예제 입력 1

첫 번째 단어인 ABAB의 경우에는 아치형 곡선으로 쌍을 연결해 보았을 때 곡선이 겹치게 되므로 좋은 단어가 아니다. 

예제 입력 1의 첫번째 예시

두 번째 단어인 AABB의 경우에는 아치형 곡선으로 쌍을 연결해 보았을 때 곡선이 겹치지 않으므로 좋은 단어이다.

세 번째 단어인 ABBA의 경우에는 아치형 곡선으로 쌍을 연결해 보았을 때 곡선이 겹치지 않으므로 좋은 단어이다.

예제 입력 1의 세번째 예시

조금 헷갈릴 수 있는 예제 입력 3도 살펴보자.

예제 입력 3의 예시

위의 사진과 같이 쌍을 이룬다면 아치형 곡선이 서로 겹치지 않게 된다.

이번 문제는 Stack을 사용하면 쉽게 해결할 수 있었다.

 

 

✨ 코드 효율
👉 메모리 : 19148 KB
👉 시간 : 264 ms
👉 코드 길이(주석 포함) : 1014 B

 

 

✔ 소스코드

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 cnt = 0;
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            Stack<Character> stack = new Stack<>();

            if(str.length()%2 != 0) {  // 문자열이 홀수면 좋은 단어x
                continue;
            }

            for (int j = 0; j < str.length(); j++) {
                if(stack.isEmpty()) {
                    stack.push(str.charAt(j));
                }else {
                    if(stack.peek() != str.charAt(j)) { // stack의 top과 다르다면
                        stack.push(str.charAt(j));
                    }else {
                        stack.pop();
                    }
                }
            }

            // 확인
            // System.out.println("stack상태는 " + stack);

            if(stack.isEmpty()) {
                cnt += 1;
            }

        }

        System.out.println(cnt);

    }

}

 

 

💡 포인트
1️⃣ 쌍이 이루어져야 하므로 단어의 길이가 홀수면 좋은 단어 ❌
2️⃣ 쌍이 이루어지는지 확인하기 위해 Stack 사용
3️⃣ 번갈아 나오는 경우에는 아치형 곡선이 교차하게 되므로 좋은 단어 ❌