99클럽 코테 스터디 9일차 TIL + 백준 3986

 

오늘의 학습 키워드

• 스택을 활용한 문자열 처리 알고리즘
• 괄호 짝맞추기와 유사한 패턴 매칭

[백준 3986 좋은 단어 문제]

문제 요약

• A와 B로만 이루어진 단어가 주어질 때, '좋은 단어'의 개수를 찾는 문제
• '좋은 단어'란 같은 글자끼리(A는 A끼리, B는 B끼리) 짝을 지었을 때, 선끼리 교차하지 않으면서 모든 글자가 정확히 하나의 짝을 가질 수 있는 단어

해결 방법

문제 해결의 핵심은 스택을 활용하여 교차하지 않는 짝 맞추기를 구현

알고리즘:

1. 문자열을 왼쪽에서 오른쪽으로 순회
2. 스택이 비어있거나 현재 문자와 스택 최상단 문자가 다르면 스택에 추가
3. 스택 최상단 문자와 현재 문자가 같으면 스택에서 제거 (짝을 이룸)
4. 모든 문자를 처리한 후 스택이 비어있으면 '좋은 단어'로 카운트

Java 코드 구현

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int goodWordCnt = 0;
        sc.nextLine();

        for(int i = 0; i < n; i++) {
            String txt = sc.nextLine();
            Stack<Character> stack = new Stack<>();
            
            for(char c : txt.toCharArray()) {
                if(stack.isEmpty() || stack.peek() != c) {
                    stack.push(c);
                } else {
                    stack.pop();
                }
            }
            
            if(stack.isEmpty()) {
                goodWordCnt++;
            }
        }
        
        System.out.println(goodWordCnt);
    }
}

오늘의 회고

What?

'좋은 단어'의 정의를 정확히 파악하는 것이 중요

How?

스택이라는 자료구조를 활용하여 교차하지 않는 짝맞추기 알고리즘을 구현