[백준 3986번] [Kotlin] 좋은 단어

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

3986번: 좋은 단어

 

난이도 : 실버 4
태그 : 자료구조, 스택

 

 

설명

 

각 단어끼리 이으면서, 선이 교차가 되면 안됩니다.

이는 스택을 사용해서 구현할 수 있겠는데요.

 

BAAB 와 같이 주어지면,

B를 스택에 넣습니다. (현재 스택 : B)

A를 스택에 넣습니다. (현재 스택 : BA)

A를 스택에 넣습니다. (현재 스택 : BAA)

새롭게 들어온 원소 A가 바로 앞에 있던 원소 A와 같으니, 제거합니다. (현재 스택 : B)

B를 스택에 넣습니다. (현재 스택 : BB)

새롭게 들어온 원소 B가 바로 앞에 있던 원소 B와 같으니, 제거합니다. (현재 스택 : 빔)

 

위와 같이, 최종적으로 스택에 아무 것도 남지 않으면 좋은 단어라 볼 수 있습니다.

 

 

 

소스코드

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    var cnt = 0

    repeat(readLine().toInt()) {
        val string = readLine()
        val stack = Stack<Char>()

        for (ch in string) {
            if (stack.isNotEmpty() && stack.peek() == ch) stack.pop()
            else stack.add(ch)
        }

        if (stack.isEmpty()) cnt++
    }
    println(cnt)
}

 

문자열을 하나씩 스택에 넣으면서,

스택이 비어있지 않으면(비어있는데 peek()을 사용하면 에러가 발생합니다),

peek()으로 바로 직전 원소를 확인해 새로 들어올 원소와 같으면 스택에서 꺼냅니다.

새로 들어온 원소와 같지 않다면, 스택에 넣습니다.

 

모든 문자열을 스택에 넣고, 스택에 아무것도 남지 않았다면 좋은 단어입니다.