🖊️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584#

---

🖊️ 1차 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    while(!prices.empty()) {
    	bool flag = false;
        int cur = *prices.begin();
        prices.erase(prices.begin());
        for(int i = 0 ; i < prices.size() ; i++) {
            if (cur > prices[i]) {
                flag = true;
                answer.emplace_back(i+1);
                break;
            }
        }
        if(!flag)
            answer.emplace_back(prices.size());
    }

    return answer;
}

처음에 Queue를 이용해서 풀려고 했는데
queue는 find가 불가능해서 걍 vector를 썼더니

보란듯이 시간초과..

Vector에서의 삭제 연산

vector에서는 특정 원소를 삭제하면
해당 원소부터 끝까지 모든 원소들이 이동해서 쭉 땡겨온다.
그래서 .. 맨 뒤에 삽입 삭제가 쉬운 것이고
사실 벡터에서 erase연산은 디게 무겁다

---

🖊️ 2차 풀이

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    queue<int> q;
    
    for(auto& p : prices) {
        q.push(p);
    }
    
    for(int i = 0 ; i < prices.size() ; i++) {
    	bool flag = false;
        int cur = q.front();
        q.pop();
        for(int j = 0 ; j < q.size() ; j++) {
            if (cur > prices[i + j]) {
                flag = true;
                answer.emplace_back(j);
                break;
            }
        }
        if(!flag)
            answer.emplace_back(q.size());
    }

    return answer;
}

그래서
아까 했던 대로..
Queue를 사용한다
대신, find를 위해 vector도 사용한다
그래서 맨 앞 원소를 삭제하기 위해 queue를 사용한다.
find할 때는 prices(vector)를 사용하고
그러면 깔꼼하다

확실히 맨 앞 원소를 삭제하는건 queue가 좋고,
vector는 너무 느린 연산이다.