문제 조건

N 명의 사람이 다른 키를 가지로 일렬로 배치 합니다.
키가 높은 사람은 앞사람이 본인 보다 작은 경우 내려 볼수 있습니다.
랜덤으로 배치된 사람이 내려다 볼수 있는 사람의 총합을 구하시요.
조건 : 내려다 보는 방향은 순서대로 (오른쪽-> 왼쪽) 한방향만 가능합니다.

예를 들어 아래 키의 순서로 N개의 배열이 제공될 때.
[0] index의 170 은 [1]150 은 내려다 볼수 있어서 1명을 내려다 볼수 있습니다.
[1] index의 150 은 [2]180 이 더 높으므로 내려다 볼수 없음.
[2] index의 180 은 [3]170, [4]160 은 내려다 볼수 있어서 2명을 내려다 볼수 있습니다.
[3] index의 170 은 [4]160 은 내려다 볼수 있어서 1명을 내려다 볼수 있습니다.
[4] index의 160 은 [5]190 이 더 높으므로 내려다 볼수 없음.
[5] index의 190 은 마지막으로 내려다 볼 대상이 없음.
각 단계가 볼수 있는 총합은 4 입니다.


[ 170, 150 , 180, 170, 160, 190]

[ 1, 0, 2, 1, 0, 0] = 4

그림으로 그리면 높이 순서는 다음과 같다. (참고용)

170 ■■■■■■■     (1 개 앞이 보임)
150 ■■■■■       (0 개)
180 ■■■■■■■■    (2 개)
170 ■■■■■■■     (1 개)
160 ■■■■■■      (0 개)
190 ■■■■■■■■■   (0 개)

위 문제는 2중 for으로 풀면 로직은 간단히 해결 할 수 있습니다.
그러나, 시간 복잡도가 O(N^2)으로 N의 행렬이 높아질때 성능이 저하되는 문제를 가지고 있습니다.
O(N) 의 시간 복잡도로 해결하는 방법을 찾는 것을 묻는 문제 입니다.

stack 자료형을 이용 합니다. (입력 값보다 높은 항목만 유지하는 정책)

접근 방법

  1. [0] index의 170 stack에 입력 
    |       |
|       |
|       |
|       |
|  170  |
---------
  2. [1] index의 150 stack에 입력 시 stack에 마지막 값(peek) 170 값이 큰값으로, stack의 item을 모두 count ( 1개 170) 
    |       |
|       |
|       |
|  150  |
|  170  |
---------
  3. [2] index의 180 stack에 입력 시 stack에 마지막 값(peek) 150 값이 작은 값은 모두 pop하고 큰값 존재할 경우에는 stack의 item을 모두 count ( 0개) 
    |       |
|       |
|       |
|       |
|  180  |
---------
  4. [3] index의 170 stack에 입력 시 stack에 마지막 값(peek) 180 값이 큰값으로, stack의 item을 모두 count ( 1개 180) 
    |       |
|       |
|       |
|  170  |
|  180  |
---------
  5. [4] index의 160 stack에 입력 시 stack에 마지막 값(peek) 170 값이 큰값으로, stack의 item을 모두 count ( 2개 170, 180) 
    |       |
|       |
|  160  |
|  170  |
|  180  |
---------
  6. [5] index의 190 stack에 입력 시 stack에 마지막 값(peek) 160 값이 작은 값으로 모두 pop시킴, stack의 item을 모두 count ( 0개 ) 
    |       |
|       |
|       |
|       |
|  190  |
---------

약간의 아이디어가 필요한 문제 입니다.
특히, 본 문제의 변형 형태로 나오는 문제가 많으며 stack 자료형의 FILO 특성을 생각하면 될 것 같습니다.

참고