Level 2 프린터

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> priorities, int location) {
5    deque<pair<int, int>> dq; // (val, 0-based location)
6    vector<pair<int, int>> order; // (0-based location, ANSWER)
7
8    for(int i=0; i<priorities.size(); ++i)  // O(n) 
9        dq.push_back(make_pair(priorities[i],i));
10    
11    while(!dq.empty()) {    // O(1) + O(n) + O(1) => O(n)  
12        if(dq.size() == 1) {    // O(1)
13            order.push_back(dq.front());
14            break;
15        }
16        
17        bool shouldPop = true;
18        auto x = dq[0];
19        for(int i=1; i<dq.size(); ++i) {    // O(n)
20            if(x.first < (dq[i]).first) {   // O(1)
21                dq.push_back(x);
22                dq.pop_front();
23                shouldPop = false;
24                break;
25            }
26        }
27        
28        if(shouldPop) { // O(1)
29            order.push_back(x);
30            dq.pop_front();
31        }
32    }
33    
34    int i=0;
35    for(auto it = order.begin(); it != order.end(); ++it, ++i) {    // O(n)
36        if(it->second == location) return i+1;
37    }
38    
39    return -1;
40}

Time Complexity

• O(N^2).
  • 예를들어 [1, 2, 3, 4, 5]와 같은 최악의 경우 연산횟수는 1 + 2 + ... + n-1 + n이 된다. 이는 n(n+1)/2 와 같기 때문에 n^2가 된다.

Space Complexity

• O(N)
  • 리스트 속 데이터의 최대갯수는 n+1개 이기 때문에 N 그대로.
  • pair를 썼지만 이는 O(2N)이기 때문에 결국 O(N)이 된다 (ref).

Other solution

1#include <bits/stdc++.h>
2using namespace std;
3#define me(a,b) max_element((a), (b))
4
5int solution(vector<int> p, int L) {
6    int answer = 0;
7    int max = *me(p.begin(), p.end());
8    
9    while (true)
10    {
11        for (int i = 0; i < p.size(); ++i)
12        {
13            if (p[i] == max)
14            {
15                ++answer;
16                if (i == L) return answer;
17
18                p[i] = 0;
19                max = *me(p.begin(), p.end());
20            }
21        }
22    }
23}

I could've used max_element()