[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 벡터를 반환해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <queue>
	using namespace std;
	typedef struct
	{
	int price;
	int idx;
	} Stock;
	vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());
	queue<Stock> q;
	for (int i = 0; i < prices.size(); i++)
	{
	if (q.empty())
	{
	q.push({ prices[i], i });
	continue;
	}
	int qSize = q.size();
	for (int j = 0; j < qSize; j++)
	{
	Stock stock = q.front();
	q.pop();
	if (stock.price > prices[i])
	{
	answer[stock.idx] = i - stock.idx;
	continue;
	}
	q.push(stock);
	}
	q.push({ prices[i], i });
	}
	for (int i = 0; i < answer.size(); i++)
	{
	if (answer[i])
	{
	continue;
	}
	answer[i] = (answer.size() - 1) - i;
	}
	return answer;
	}
	int main(void)
	{
	vector<int> prices = { 1, 2, 3, 2, 3 };
	vector<int> answers = solution(prices);
	for (int answer : answers)
	{
	cout << answer << " ";
	}
	cout << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

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