[Swift Algorithm] 옥상 정원 꾸미기 BOJ #6198

문제 설명

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

 

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

 

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

입출력 예제

입력

6
10
3
7
4
12
2

출력

5

 

내 문제 풀이

import Foundation

let count = Int(readLine()!)!
var result = 0
var stack = [Int]()

for i in 0..<count {
    let h = Int(readLine()!)!
    
    // 스택이 비었을 때 (가장 첫 옥상 높이 삽입을 위함)
    if stack.isEmpty {
        stack.append(h)
    }
    // 스택이 비어있지 않을 때
    else {
        // 만약 스택의 마지막 옥상 높이가 현재 입력된 높이보다 높을 때
        if stack[stack.count-1] > h {
            stack.append(h)
        }
        // 만약 스택의 마지막 옥상 높이가 현재 입력된 높이보다 낮을 때
        else {
            while stack[stack.count-1] <= h {
                stack.removeLast()
                result += stack.count
                if stack.isEmpty { break }
            }
            stack.append(h)
        }
    }
    
    // 마지막 수가 입력, 위의 과정을 거치고도 stack의 길이가 1 이상일 경우
    if i == count-1 && stack.count > 1 {
        for _ in 0..<stack.count-1 {
            stack.removeLast()
            result += stack.count
        }
    }
}

print(result)

(이 문제는 #2493번 탑 문제와 정말 유사하므로, 함께 풀어보시는 것을 추천드립니다.)

풀이를 나열하기 전, 내가 이 문제를 보는 시선에 대해 설명한다.
해당 문제 설명에서는 한 옥상이 관찰 가능한 옥상의 수들의 합을 구하라 하였지만,
나는 한 옥상마다 관찰 가능한 다른 옥상들의 합을 구하는 것으로, 역으로 풀이했다.

• 맨 처음 입력되는 옥상 높이의 스택 push를 위해 isEmpty를 이용해주었다.
• 두 번째 입력되는 옥상부터는 스택에 존재하는 마지막 요소와 높이를 비교했다.
• 현 옥상이 스택의 마지막 요소보다 낮다는 것
  == 스택 마지막 요소에 해당하는 옥상의 앞을 가리지 않음.
  && 이 옥상 또한 앞으로 입력될 옥상 중 관찰 가능한 옥상 존재 가능성 있음.
  따라서, 이 때는 result에 개수를 누적하지 않고 스택에 해당 옥상의 높이를 추가해주기만 한다.
• 현 옥상이 스택의 마지막 요소보다 높다는 것
  == 이 옥상이 스택 마지막 요소 옥상의 앞을 가림.
  && 이 옥상은 앞으로 입력될 옥상 중 관찰 가능한 옥상 존재 가능성 있음.
  따라서, 이 때는 스택에 입력되어있는 옥상 중 더이상 새로운 옥상 관찰이 불가한 옥상들을 삭제하고,
  삭제되는 옥상들은 자기 자신을 관찰한 옥상이 몇개인지 세어주는 역할의 반복문을 만들어주었다.
• 반복문은 스택의 마지막 요소 옥상이 현 입력 옥상보다 낮은동안 시행하게 했고,
  removeLast를 이용하여 스택의 마지막 옥상을 하나씩 삭제했다.
• result에는 삭제된 옥상을 관찰한 옥상의 개수를 누적해줘야하는데,
  따라서 해당 옥상을 삭제하고 남은 스택의 옥상 개수를 result에 더해주었다.
  (해당 옥상보다 낮거나 중간에 가려져 관찰하지 못한 옥상은 이미 스택에서 삭제됐기 때문.)
• 그리고 현 입력 옥상이 옥상 중 가장 높은 옥상일 경우, 스택의 옥상을 모두 삭제해버릴 수 있기 때문에
  스택이 비게 될 경우 반복문을 탈출하도록 해주었다.
• 반복문이 끝나면 스택에 현 옥상 높이를 추가했다.
• 마지막 옥상이 입력된 경우에는, 스택의 길이를 확인해주어 1보다 클 경우
  스택 길이만큼 위 while문과 같은 내용의 반복문을 생성해주었다.
  (마지막 옥상이 입력되고, 연산을 모두 수행했는데도 스택의 길이가 1보다 크다는 것은
  현재 스택에 남은 옥상들의 관찰 개수가 측정되지 않았다는 뜻이므로.
  ex) 문제에서 주어진 예제의 경우 마지막에 [12, 2] 스택이 남게된다.
  2는 12보다 작기때문에 스택에 추가만되고 결과에 누적되지않는다.)

 

💡 피드백

• 바로 이전에 풀었던 문제와 너무 비슷하여 금방 풀 수 있었다.
• 이런 풀이 방법을 복습하게 됐고, 확실히 이해하게되어 앞으로도 활용가능할 것 같다.
• 결과로 메모리나 시간이 많이 필요하다고 나와서,, 코드 개선이 필요할 것 같다.

 

---

 

 

문제

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