[백준] 3986. 좋은 단어 (JAVA)

이번에 풀어 볼 문제는 <백준 3986번. 좋은 단어>이다.

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

📌 문제 탐색하기

목표

입력된 단어 중 좋은 단어의 개수 세기

해야 할 것

1. 좋은 단어를 어떻게 판별할까?

➡️선끼리 교차하지 않으면서 각 글자를 정확히 한개의 다른 위치에 있는 같은 글자와 짝 지을 수 있는 단어

(예시 : ABAB는 좋은 단어x, AABB는 좋은단어, ABBA는 좋은 단어 )

입력

[첫줄] 단어의 수 N ( 1 ≤ N ≤ 100)

[둘째줄 ~ ] 단어 ( 2 ≤ 단어의 길이 ≤10^5)

아이디어

1. 좋은 단어를 어떻게 판별할까?

 

이전에 푼 괄호 문제와 거의 유사한 유형의 문제이다.

2024.12.15 - [STUDY/알고리즘&코딩테스트] - [백준] 4949. 균형잡힌 세상 (JAVA)

 

이 문제 역시 스택의 특성을 활용하면 주어진 조건대로 선을 교차하지 않고 문자를 짝지어 제거할 수 있다.

 

예를 들어, 스택의 맨 위에 'A'가 있을 때 새로 입력된 문자가 또 'A'라면, 두 문자는 서로 짝이 지어 제거될 수 있다. 이는 두 문자가 짝을 이루면서 스택에서 제거되므로 선이 교차하지 않음을 의미한다.

'B'도 동일하게 처리된다. 스택의 맨 위가 'B'일 때 새로 입력된 문자가 'B'라면, 두 문자는 짝을 지어 스택에서 제거된다.

 

만약 스택이 비어있거나, 스택의 맨 위 문자와 새로 입력될 문자가 짝이 될 수 없다면 스택에 새로 입력될 문자를 쌓는다.

 

이 과정을 반복하여 모든 문자가 짝을 이루어 스택이 비게 되면 해당 단어는 "좋은 단어"로 판단할 수 있다.

반대로 모든 과정을 거친 뒤에도 스택에 문자가 남아 있다면 해당 단어는 "좋은 단어"가 아니다.

 

📌 코드 설계하기

1. input 명령을 받고 스택을 구현한다.

2. 좋은 단어의 수를 셀 변수 count를 초기화한다.

3. 한 글자씩 읽으며 다음과 같이 실행한다.

3-1. 스택이 비어있지 않으면서, 스택의 가장 윗 원소와 현재 입력할 글자가 짝이 맞다면? ➡️ 해당 문자를 스택에서 제거한다.

3-2. 스택이 비어있거나 스택의 가장 윗 원소와 현재 글자를 짝 지을 수 없으면? ➡️ 현재 글자를 스택에 삽입한다. 

4. 모든 글자에 대해 3번 과정을 반복한 뒤, 스택에 문자가 남아있지 않다면 count 값을 증가시킨다.

5. 모든 input 단어들에 대해 3,4 과정을 반복한다.

📌 정답 코드

import java.util.ArrayDeque;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = 0;

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

        for(int i =0; i<N; i++){
            char[] input = br.readLine().toCharArray();

            ArrayDeque<Character> stack = new ArrayDeque<>();

            for(char c : input){
                if(!stack.isEmpty()&&stack.peek()==c){
                    stack.pop();
                }else {
                    stack.push(c);
                }
            }

            if(stack.isEmpty()){
                count++;
            }
        }

        System.out.println(count);
    }
}

 

➡️이 풀이는 단어의 길이만큼 스택에 넣고 빼는 과정이 필요하기 때문에 최악의 경우 10^5만큼의 연산을 해야한다.

➡️단어의 개수 N은 최대 100 이므로 전체 시간복잡도는 O(100*10^5) = O(10^7) 이 된다. 이 정도는 제한 시간 1초 내에 충분히 수행 가능하다.

📌 알게 된 것

스택을 사용하는 문제 유형들은 어느정도 틀이 정해져 있는 것 같다. 해당 문제 유형들을 익혀두자.