[Programmers 코딩테스트 고득점 Kit] 주식가격

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

벡터 크기가 최대 100,000이기 때문에 단순 O(N^2)으로는 풀 수 없는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. prices 벡터를 순회하며 주식 가격과 인덱스를 큐에 넣어줍니다.

2. 큐에 넣어주기 전에 기존 큐에 들어가 있는 주식 가격들과 현재 보고 있는 주식 가격을 비교한 뒤 현재 주식 가격이 기존 주식 가격보다 하락했을 경우 answer 벡터에 표시를 해줍니다.

3. prices 벡터를 끝까지 순회했는데도 한 번도 하락한 적이 없어 answer 벡터에 표시하지 못한 주식들이 있을 겁니다. 이러한 주식들에 대해 answer 벡터를 업데이트해줍니다.

4. answer 벡터를 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~