[백준] 10799 쇠막대기

 

🔒 문제

 

🧠 아이디어

"()"을 모두 '*'로 미리 대치한다.

 

 

🔑 풀이 1. Kotlin Code

')' 을 만날 때마다 이전 '(' 까지 pop 하며 *의 개수를 카운팅하는 무식한 방법으로 풀이했다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))

    val str = bufferedReader.readLine().replace("()", "*")
    val stack = Stack<String>()

    var answer = 0

    for (char in str) {
        when (char) {
            '*' -> {
                if (stack.isEmpty()) continue
                stack.push(char.toString())
            }
            '(' -> {
                stack.push(char.toString())
            }
            ')' -> {
                var starCnt = 0
                while (stack.isNotEmpty()) {
                    if (stack.peek() != "(") {
                        val star = stack.pop()
                        starCnt += star.length
                    } else {
                        stack.pop()
                        stack.push("*".repeat(starCnt))
                        answer += (starCnt + 1)
                        break
                    }
                }
            }
        }

    }

    print(answer)

}

 

 

🔑  풀이 2. Kotlin Code

stack 에 '('이 나올 때마다 무조건 담아둔다.

stack 에 담긴 '(' 의 수는 곧 '막대기의 수'다.

따라서, '*'을 만날 때마다 스택에 담긴 원소 수(관통할 막대기의 수) 만큼을 더해주면 레이저(*)를 쏴서 생긴 막대 조각의 왼쪽에 있는 것들의 개수를 구할 수 있다.

')'는 막대기의 끝을 의미하므로 만날 때마다 막대 개수 +1 해주고 stack 에서 담겨있던 '('를 하나 빼준다.

 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))

    val str = bufferedReader.readLine().replace("()", "*")
    val stack = Stack<Char>()

    var answer = 0

    for (char in str) {
        when (char) {
            '*' -> {
                answer += stack.size // 걸쳐있는 막대 개수만큼 추가
            }
            '(' -> {
                stack.push('(')
            }
            ')' -> {
                answer++ // 막대의 끝부분만 추가
                stack.pop() // 한 막대가 범위 밖으로 끝남
            }
        }

    }

    print(answer)

}