매일의 주식 가격이 담긴 리스트가 있다.
모든 날에 대해 해당 날짜에 샀을 때 이득을 보려면 얼마나 시간이 걸리는가 알아보시오. 이득을 못보면 -1.
[1,3,2,5,4] => [1,2,1,-1,-1]
뒤에서부터 탐색하면서 가장 최근에 나오고 비싼 주식만 들고 다니면서 날짜를 계산하는 방법으로 했는데, 제가 자료구조가 부족한 탓에 매번 리스트를 선언하게 되서 결국 N^2이 되더라고요. NlogN 없을까요.
모든 날에 대해 해당 날짜에 샀을 때 이득을 보려면 얼마나 시간이 걸리는가 알아보시오. 이득을 못보면 -1.
[1,3,2,5,4] => [1,2,1,-1,-1]
뒤에서부터 탐색하면서 가장 최근에 나오고 비싼 주식만 들고 다니면서 날짜를 계산하는 방법으로 했는데, 제가 자료구조가 부족한 탓에 매번 리스트를 선언하게 되서 결국 N^2이 되더라고요. NlogN 없을까요.
최댓값 세그 짜고 이분탐색하면 Nlog^2N 나와요
그르네요 트리로 구현할걸.. 감사함당
뒤에서 부터 set에 { price[day], day } 를 삽입한 다음에 upper_bound로 price[day] 보다 큰 수가 존재 하는 지 확인하면 되지 않을까요??
내 뒤에 나보다 큰 값이 언제 나오는지 확인해야 하는 거면 set 등으로 확인할수 있겠죠 - dc App
스택 쓰면 O(N) 에 됩니다
? 프로그래머스에서 본 것 같은데
스택으로 푸는 법은 같은문제인
https://acmicpc.net/problem/2493
풀이를 찾아보자
도와주신 분들 정말 감사합니다!