[Swift 알고리즘] stoneWall - Codility

StoneWall coding task - Learn to Code - Codility

---

문제 분석 (틀림)

문제 분석
막대 그래프를, 직사각형으로만 구성하기 위해 필요한 최소 개수는?
막대의 높이가 최대 10억이므로, 일반적인 탐색 문제는 아닌 듯하다.
왼쪽부터 현재 원소의 값(높이)를 기준으로, 연속으로 확장 가능한 너비를 측정한다.
현재 값보다 작은 값을 만나면 멈춘다. 직사각형을 1개를 구성한다.
    구성이 완료된 부분은, 각 원소에서 현재 값만큼 빼준다.
    직사각형 개수를 += 1
그런데 이렇게 하면, O(N^2)으로 시간 초과가 난다..

문제 분석 (구글링)

 스택에 저장된 높이와 현재 높이를 비교하면서 다음을 실행한다.
     1. 저장된 높이가 더 높은 경우: 현재 더 낮은 높이 블럭이 생길 것이므로, 이어지던 직사각형 생성 과정이 종료되었다. 이후 판단 과정에서 저장된 높이들이 필요 없어졌다. 현재보다 더 높은 블럭을 모두 스택에서 제거한다.
     2. 같은 경우: 아무 것도 하지 않는다. 블럭을 아끼는 것이다.
     3. 저장된 높이가 더 낮은 경우: 더 높은 새로운 블럭이 필요하다. 개수를 세고, 스택에 추가한다.

풀이 (구글링)

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var stack: [Int] = []
    var count = 0

    for element in H {
        while !stack.isEmpty && stack.last! > element {
            stack.removeLast()
        }

        if stack.isEmpty || stack.last! < element {
            count += 1
            stack.append(element)
        }
    }

    return count
}

회고

분명 Easy인데, 꽤나 어려운 문제였다.

인간의 직관과는 다른 컴퓨팅 사고가 필요한 문제에 여전히 고전한다.

이 문제는 3가지 케이스를 생각해내는 것이 핵심이다.

stack.top과 탐색 중인 element을 비교한다. 비교값은 3가지 케이스를 갖는다.

1. 같은 경우:
   1. 패스한다.
2. element가 더 작은 경우:
   1. stack의 더 높은 막대들은, element를 만들 수 없다.
   2. 동시에 1.의 케이스로 이어지던 직사각형의 생성 과정이 종료된다.
   3. 생성이 종료된 높은 막대들은 이후 판단 과정에 필요 없다. 모두 제거한다.
3. element가 더 큰 경우:
   1. 새로운 높은 막대가 필요하다.
   2. count를 증가시키고, stack에 element를 추가한다.

 

참고

https://rkdvnfma90.tistory.com/261