Lesson7. Stacks and Queues - StoneWall

StoneWall - Cover "Manhattan skyline" using the minimum number of rectangles.

https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

문제요약

벽돌 벽을 쌓는다. N미터의 직선길이로 위치마다 높이가 모두 다르다. 각 위치의 높이가 N개의 양의 정수 배열 H로 주어지고 H[I]는 I부터 I+1미터까지의 높이를 의미한다. 벽돌 벽은 직사각형 block들로만 이루어진다고 할 때, 주어진 H를 만족하는 최소한의 block수를 계산한다.

Assume that:

N is an integer within the range [1..100,000];

each element of array H is an integer within the range [1..1,000,000,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

벽을 아래의 동일 높이의 block들로 순서대로 쌓아 올린다고 가정하면, 높이가 증가하는 경우에는 최초 높이 만큼은 block 하나로 쌓을 수 있다.

즉 높이가 [1,2,3]이면 높이 1만큼은 3미터 block하나로 가능하다. 높이가 [1,2,3,2,1]이라면 마찬가지로 높이 1의 5미터 block하나로 가능하고, 다음 층은 높이 1의 3미터 block으로, 마지막 층은 높이 1의 1미터 block으로 총 3개의 block이 필요하다.

즉 높이가 높아지는 경우에는 그 높아진 층에 대해서 추가 block이 필요하고, 낮아질 경우에는 이전에 그 높이가 이상의 높이가 있다면 상관없지만 이전에 등장한 높이가 더 낮다면 마찬가지로 추가 block이 필요하게 된다. 높이가 만약 이전과 동일하다면 하나로 처리가능하므로 무시해도 된다.

[1,2,4,3,2]라면 1을 쌓고, 2와 4에서 높이가 높아졌으므로 1개씩 더 필요하므로 3개가 필요하고 3에서는 이미 높이가 낮아져서 4는 고려하지 않아도 되고 이전이 2였으므로 3은 추가로 하나가 더 필요하게 되어 4개, 2에서는 이전 3은 고려되었으므로 무시하고 이전 높이가 2이므로 동일해서 추가로 필요하지 않게 된다. 따라서 총 4개가 필요하다.

정리하면 stack에 하나씩 넣어가면서 개수를 증가하는데 높이가 동일하면 패스, 높아지면 넣고 증가, 낮아지면 해당 높이보다 높은 값을 stack에서 제거하고 다시 비교한다.