[프로그래머스 - level2] [스택/큐] 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

 

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

1번을 제외하고 오답이 나올때는 prices = {1, 2, 3, 2, 3, 1} return {5, 4, 1, 2, 1, 0}의 예를 하나씩 따라가면서 이해하면 풀린다

 

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

<문제 이해를 돕기 위한 재해석>
문제설명
n초 간의 주가를 초 단위로 기록한 배열 prices가 매개변수로 주어질 때, 각 초의 주가를 기준으로 해당 초 부터 n초 사이에 가격이 떨어지지 않은 시간은 몇 초인지 배열에 담아 return 하도록 solution 함수를 완성하세요.
입출력 예
prices : [1, 2, 3, 2, 3]
return : [4, 3, 1, 1, 0]
입출력 예 설명
1초의 주가는 1이며 1초부터 5초까지 총 4초간 주가를 유지했습니다.
2초의 주가는 2이며 2초부터 5초까지 총 3초간 주가를 유지했습니다.

3초의 주가는 3이며 4초의 주가는 2로 주가가 떨어졌지만 3초에서 4초가 되기 직전까지의 1초간 주가가 유지 된것으로 봅니다. 따라서 5초까지 총 1초간 주가를 유지했습니다.
위의 예시를 이해하실때
'현재가격을 기준으로 1초후 다음 가격이 떨어졌다면 이후에 가격은 상관없이 가격이 떨어지지않은 기간은 1초로 간주한다'로 이해하셔야 문제에서 요구하는 답을 낼 수 있는것 같습니다.
따라서 문제 예시에서도 3->2초 , 다시 2->3초로 가격이 상승하여도 해당 3초시점의 가격은 1초간 떨어지지 않은 것으로 간주하고 있습니다.

4초의 주가는 2이며 4초부터 5초까지 총 1초간 주가를 유지했습니다.
5초의 주가는 3이며 5초 이후로는 데이터가 없으므로 총 0초간 주가를 유지했습니다.

---

 

풀이 과정

주가 prices[i] 를 queue에 반복문으로 넣는다는 개념

-> 이유: queue를 쓴 이유는 제일 첫번째 들어온 원소보다 작은 값이 들어올 때 까지 주가가 유지되는 것이기 때문 

내부 반복문에서 queue에 front보다 작은 값이 들어올 때 까지 prices[j] push/ push된 카운트를 저장할 iAnswer 변수

push해줄때 마다 iAnswer++

queue에 front보다 작은 값이 들어왔다면 iAnswer++ 해 준 다음 내부 반복문 break. 

-> 이유: 다음 초에 가격이 떨어지더라도 1초간 가격을 유지한걸로 보기 때문에 iAnswer++로 1초를 더해주는 것

내부 반복문 끝나면 외부 반복문에서 answer에 push

인덱스인 i가 마지막 인덱스면 answer에 0 push

 

 

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> prices) {
	vector<int> answer;
	int iAnswer =0;
	for (int i = 0; i < prices.size(); ++i) {
        if(i < prices.size()-1) {
            queue<int> seconds;
            seconds.push(prices[i]);
            for(int j=i+1;j<prices.size();++j) {
                if(seconds.front() <= prices[j]) {
                    seconds.push(prices[j]);
                    ++iAnswer;
                }
                else
                {
                    ++iAnswer;
                    if(seconds.size() == 1) {
                        iAnswer = 1;
                    }
                    break;   
                }
            }
            answer.emplace_back(iAnswer);
            iAnswer = 0;
        }
        else {
            answer.emplace_back(0);
        }
    }

	return answer;
}

근데 내가 푼 방식은 시간복잡도가 O(n^2)일텐데 효율성 테스트가 통과하는게 요상하다.

일단 제대로 된 질문 해석이랑 테스트케이스 보고 로직 짜서 바로 해결한 문제!