백준 3986번 좋은 단어 [Stack] :: 마이구미

이번 글은 백준 알고리즘 3986번 "좋은 단어" 를 다뤄본다.

이 문제는 스택을 통해 접근하는 문제이다.

백준 3986번 좋은 단어 - https://www.acmicpc.net/problem/3986

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 

만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 갯수를 세는 것을 도와주자.

문제만 보면, 바로 쉽게 이해하기는 힘들 수 있다.

먼저 예를 통해 문제를 이해해보자.

ABAB 주어졌을 경우를 보자.

1. ABAB => A와 A 위로 아치형 곡선을 그린다.

2. ABAB => B와 B 위로 아치형 곡선을 그린다.

1번 후 2번을 그려볼 때, 아치형 곡선이 겹치는 것을 확인 할 수 있다.

위와 같은 그림이 될 수 있겠다.

빨간색을 보듯이 겹침으로써, 이 단어는 좋은 단어가 아니다.

즉, 좋은 단어의 기준은 겹치는 부분이 없어야한다.

AABB 와 ABBA의 경우를 보자.

겹치는 부분이 존재하지 않으므로 좋은 단어인 것을 알 수 있다.

그렇다는건, 결국 A와 B가 인접해있으면 좋은 단어라는 것이다.

ABBA의 경우는 BB를 뺏을 때,  AA가 됨으로 인접해진다.

위의 규칙을 스택을 활용하여 접근할 수 있다.

1. 스택에 알파벳을 넣는다. (push)

2. 스택의 맨 위에 있는 알파벳과 넣을 알파벳이 같다면 뺀다. (pop)

위의 처리가 올바르게 된다면 좋은 단어이다.

그렇다면, 처리가 되지 않는다면 좋은 단어가 아니라는 것을 알 수 있다.

말하자면, 스택의 top을 비교하면서 push, pop을 구별하면 된다.

아래 소스를 보자.

for(int i=0;i<len;i++) {

    if (!stack.isEmpty()) {
        if (stack.peek() == array[i]) {
            stack.pop();
        } else {
            stack.push(array[i]);
        }
    } else {
        stack.push(array[i]);	
    }

}

정말 간단하다.

top과 다음 값을 비교하면서 같다면 pop 그렇지 않으면 push를 하면 된다.

스택이 공백인 상태에서 비교를 할 수는 없으므로 isEmpty를 통해 먼저 구분하였다.

이 문제는 스택 응용에 있어 가장 기본적인 문제라고 생각이 들어 다뤄보았다.

전체 소스는 아래 링크 Github에서 확인하길 바란다.

백준 3986번 좋은 단어 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/3986.java