[백준] 3986번 : 좋은 단어 – JAVA [자바]

 

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

3986번: 좋은 단어

 

 

---

 

• 문제

 

 

---

• 문제 풀이

백준 3986번 좋은 단어는 스택을 이용해서 푸는 실버 4 문제이다. 스택에 대해서 조금 더 구체적으로 알고 싶으면 밑에 링크를 참고하면 좋겠다.

 

https://propercoding.tistory.com/entry/자료구조-스택Stack

[자료구조] 스택(Stack)

 

이 문제에서는 A와 B로만 주어진 단어가 있고 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 지어 아치형 곡선을 만든다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을 수 있다면, 그 단어는 '좋은 단어'가 되고 좋은 단어의 개수만 파악하면 되는 문제이다. 

 

예시들을 보겠다.

 

       1. ABAB                            2. AABB                          3. ABBA                                      4. ABBABB

따라서 ABAB의 아치형 곡선은 교차하므로 ABAB를 제외하고는 모두 다 '좋은 단어'가 된다.

 

이 문제는 스택 문제이므로 스택을 이용해서 풀도록 하겠다.

 

단어의 첫 글자, 즉 인덱스 0을 스택에 push 해서 시작한다.

그리고 인덱스 1부터 끝까지 스택에서 peek 한 거와 비교해서

1) 만약 stack.peek() == string.charAt(index) 이면 스택에서 pop 해주고

2) 만약에 stack이 비어있거나 또는 stack.peek() != string.charAt(index) 이면 stack.push(string.charAt(index)) 해주면 된다.

 

그리고 끝에 스택이 비어있으면 좋은 단어이고 만약에 스택이 비어있지 않으면 좋은 단어가 아니게 된다.

 

 

---

• 코드

import java.util.*;
import java.io.*;
public class Main {
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        count = 0;
        for (int i = 0; i < t; i++) {
            String s = br.readLine();
            goodWordCheck(s);
        }
        System.out.print(count);
    }

    static void goodWordCheck(String s) {
        if (s.length() % 2 == 1) return; //문자열의 길이가 홀수이다는 것은 A 또는 B의 개수가 홀수이므로 좋은단어 X
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0)); //첫 단어는 스택에 push
        for (int i = 1; i < s.length(); i++) {
            if (stack.size() > 0 && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }
        if (stack.isEmpty()) count++;
    }
}

 

 

---

• 후기

비록 실버 4 난이도의 스택 문제였지만 스택 문제를 풀어본 경험이 많이 없으면 어려울 수 있는 문제였던 거 같다.