BOJ Algorithm

옥상정원 꾸미기

도시에는 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번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

---

느낀점 및 풀이법

• 해당 문제는 Stack을 이용하여 푸는 문제입니다.
• 제가 푼 방식은 빅오표기법 O(n)에 해당하여, 큰 실행시간을 잡아 먹습니다.
• 이를 Stack으로 풀게 된다면 O(n^2)까지 줄어 들게 되어 훨씬 효율적인 코드가 완성됩니다.
• 코드에 대한 이해 부족으로 단순 반복문을 이용하여 풀었습니다.