<백준> 탑 보기(Gold 3)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/22866 탑 보기 at main · heesoo-park/ForCodeKata

제출 결과

---

뭔가 이전에 풀었던 문제와 비슷한 거 같은데 전에 풀었던 방법이 정확히 기억나지 않고 어떤 걸 사용했었는지만 생각나던 문제였다.

이런 탑 문제를 보면 이제는 가장 먼저 그냥 완전탐색을 써서 돌리는 건 안 되는 문제겠구나라는 생각을 많이 하게 된다.

숫자 제한이 보통 시간 제한을 넘어가기 때문이다.

그래서 사용하는 건 스택이다.

스택을 사용해서 조건에 맞춰 요소를 빼고 넣으며 반복문 한 번에 알고리즘이 진행되도록 한다.

 

그래서 스택을 머릿속으로 사용해야겠다 하고 코드를 짜봤는데 짜고나서보니까 완전탐색과 다름이 없는 코드가 나왔다.

제출했더니 당연히 시간초과가 나왔다...

전에 다른 문제도 분명 이런 식으로 처음에 풀고 다른 방법으로 넘어갔던 거 같은 느낌이 온다.

 

그래서 예전에 풀었던 문제들을 뒤져보고 다른 사람들의 풀이를 참고도 해보면서 방법을 찾은 건 하나씩 순회하지만 먼저 스택에 넣는 작업부터 하는 게 아니라 스택에서 빼는 작업을 먼저 해야한다는 것이다.

그렇게 했을 때 스택에 남아있는 원소의 개수를 보고 현재 위치에서 보이는 건물의 개수를 알 수 있고 보이면서도 가장 옆에 있는 건물의 번호도 알 수 있다.

 

하지만 이렇게 정방향으로 한 번만 하면 현재 위치에서 좌측만 고려하게 된다.

그렇기 때문에 역방향으로도 한 번 순회하여 현재 위치에서 우측에 있는 건물들도 고려해줬다.

반대 방향을 진행할 때는 건물 개수를 구할 때 기존 정방향에서 구한 값에다가 더해줬다.

문제에서 원하는 것도 좌우 모두를 고려하는 것이기 때문이었다.

대신에 고려할 것은 우측에서 구한 가장 가까운 건물 번호가 이전에 좌측에서 구한 가장 가까운 건물 번호보다 현재 건물 번호의 차를 구했을 때 더 작다면 가장 가까운 건물 번호를 우측에서 구한 가장 가까운 건물 번호로 변경해야한다는 것이다.

가장 가까운 건물를 구할 때는 절댓값을 사용해야하고 이게 동일할 때는 더 작은 번호를, 다를 때는 절댓값이 더 작은 번호를 사용해야하기 때문이다.

 

도움이 없었다면 풀어내기에 매우 어려웠을 문제였지만 하나하나 단계를 디버깅하며 확인해보니까 이제 좀 더 이해가 되는 느낌이다.

탑 문제가 나오면 일단 스택에서 빼는 걸 먼저 해자는 생각을 가져야겠다.(아닌 케이스도 많겠지만)

 

그리고 틀린 케이스는 왜 그랬냐면 가장 가까운 건물 번호를 저장하는 배열을 -1로 초기화한 것이 문제였다.

-1로 하다보니 역방향 순회시 조건을 체크하는 코드에서 원하는 흐름이 나오지 않는 케이스가 발생했다.

건물 번호가 1일 때 계속 발생하는 걸 알게 되면서 수정했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.Stack
import java.util.StringTokenizer

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()

    val n = br.readLine().toInt()
    val buildings = IntArray(n + 1)
    val proximate = IntArray(n + 1) { -100000 }
    val count = IntArray(n + 1)

    val st = StringTokenizer(br.readLine())
    for (i in 1..n) {
        buildings[i] = st.nextToken().toInt()
    }

    var stack = Stack<Int>()
    for (cur in 1..n) {
        while (stack.isNotEmpty() && buildings[stack.peek()] <= buildings[cur]) stack.pop()

        count[cur] = stack.size
        if (count[cur] > 0) proximate[cur] = stack.peek()
        stack.push(cur)
    }

    stack = Stack<Int>()
    for (cur in n downTo 1) {
        while (stack.isNotEmpty() && buildings[stack.peek()] <= buildings[cur]) stack.pop()

        count[cur] += stack.size
        if (stack.isNotEmpty() && stack.peek() - cur < cur - proximate[cur]) proximate[cur] = stack.peek()
        stack.push(cur)
    }

    for (i in 1..n) {
        if (count[i] != 0) sb.append("${count[i]} ${proximate[i]}\n") else sb.append("0\n")
    }
    print(sb)
}

 

참고)

https://yerinpy73.tistory.com/424