• 백준 3986번 좋은 단어 [Stack] :: 마이구미
    알고리즘 풀이/스택, 큐 2017. 1. 16. 21:00
    반응형

    이번 글은 백준 알고리즘 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

    반응형

    댓글

Designed by Tistory.