주식가격

https://programmers.co.kr/learn/courses/30/lessons/42584?language=cpp# 

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

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

int firstMin(const std::vector<int>& target, int value, int startIndex) {
    int c = 0;
    for (int i = startIndex; i < target.size(); ++i) {
        if (target[i] < value) {
            return ++c;
        }
        ++c;
    }

    return c;
}

vector<int> solution(vector<int> prices) {
    std::vector<int> answer;
    int loopIndex = 0;
    while (true) {
        const int front = prices[loopIndex++];
        if (loopIndex == prices.size()) {
            answer.push_back(0);
            break;
        }

        int idx = firstMin(prices, front, loopIndex);
        answer.push_back(idx);
    }

    return answer;
}

 

 

o(n2) 으로 해서 좋지 않은듯

 

참고로 const & 안붙여서 시간초과 떳다가 고치니 해결됐음

 

문제 포인트는 탐색하는 인덱스를 기억했다가 처음부터 재탐색 하지 않도록 하는 것

 

스택/큐 문제인데 스택 큐 이용해서 풀어봐야겠다