내 기준 어려운 문제였다.
사고가 필요한 문제.
컨셉은 스택을 오름차순으로 쌓아나가는 것이다.
prices 배열에 순차적으로 접근해서 스택에 값을 추가하는데,
이때 prices값이 스택의 가장 위에 값보다 작다면,
가격이 떨어진 것이니 값을 업데이트 해준다.
이 때 while문을 써야 한다.
스택 맨 위에 값만, prices[i]값보다 작다는 보장이 없기 때문이다.
예를 들어, 이러한 경우가 있을 수 있다.
[2 3 1 1]의 경우 [2,3]까지 stack을 쌓아둔 상태에서 prices[2]를 만나면 prices[2]는 1이니, stack맨 위 값 3 보다 작다.
하지만 prices[2]는 stack 맨 위 바로 아래 값 2보다도 작다.
한마디로 배열의 두번째 요소도 세번째 요소보다 작지만, 배열의 첫번째 요소도 세번째 요소보다 작다.
이 부분도 고려해야되기 때문에, while문을 사용해야 한다.
저번에도 왼큰수, 오큰수 문제와 비슷한 방식인 것 같은데, 오랜만에 보니 새롭다.
이런 유형 제대로 익혀둬서
실제 코테에 출제된다면 꼭 맞추고 싶다.
...