프린터

문제

구해야 하는 결과 값은 뭘까?

이걸 쓰는 이유는 자꾸 이상한 답을 구하고 있어서이다. 문제를 분석하는 능력을 더 키울 필요가 있다고 생각을 했다.

priorities는 작업이 진행 되는 순서와 작업의 우선순위를 나타내는 배열이다.
이 배열안에 작업은 앞쪽 인덱스의 작업부터 실행이 된다. 하지만 만약에 배열 안에 자신보다 큰 우선순위를 가진 작업이 있다면 실행하던 작업을 배열의 마지막으로 보낸다.

구해야 하는 결과 값은
location 변수의 값을 인덱스 값으로 하는 요소가 몇번째로 실행이 되는지이다.

---

문제의 시간복잡도

문제의 n값의 범위는 100이다. 그렇기 때문에 $O(n^3)$ 시간복잡도 이하의 알고리즘으로 작성을 해야 한다고 생각을 하였다.

---

문제의 접근방법

먼저 생각한 것은 priorities 내부의 작업이 선입선출의 구조인 큐의 구조를 가지고 있다고 생각을 했습니다.

다음 생각한 것은 priorities 배열에서 첫번째 요소가 가장 높은 우선순위를 가지고 있는가?를 찾기 위해서 배열의 최댓값을 찾는 연산이 필요하다고 생각을 하였습니다.

그리고 생각 한 것은 priorities 내부의 요소의 값에 location과 비교할 인덱스 값을 추가해야 한다고 생각을 하였습니다. 현재 priorities 내부의 있는 값들은 작업이 실행이 되면서 순서가 바뀌기 때문에 초기의 인덱스를 기억할 필요가 있다고 생각을 했습니다.

---

답

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>


using namespace std;

bool compare(pair<int,int> a, pair<int,int> b){
    return a.first < b.first;
}


int solution(vector<int> priorities, int location) {
    deque<pair<int, int> > v;
    int answer = 0;
    
    for(int i=0;i<priorities.size();i++)
    {
        v.push_back(make_pair(priorities[i],i));
    }
      
    while(true)
    {
        pair<int,int> res;
    
        auto max = *max_element(v.begin(), v.end(), compare);
    
        while(v.front().first != max.first)
        {
            v.push_back(v[0]);
            v.pop_front();
        }
        
        res=v[0];
        v.pop_front();
        answer++;
        
        if(res.second == location)
            return answer;
    }

}

풀이의 시간 복잡도

최악의 경우 while문을 $1+2+3+4+... + (n-1)+(n)$ 번이 걸려서 $O(n^2)$ 정도의 시간이 걸릴 것이다. 근데 while문 내부에 max_element 함수가 $O(n)$의 시간이 걸리기 때문에 총합적으로 $O(n^3)$의 시간이 걸린다.

---

몰라서 참고했던 부분

pair의 선언

deque<pair<int, int> > v;

v.push_back(make_pair(priorities[i],i));

stl container에 pair요소를 삽입 할 때에는 make_pair(x, y) 함수를 이용하여 pair를 생성하고 삽입하여야 한다.

---

deque(덱)

#include <deque>


deque<pair<int, int> > v;

v.push_back(v[0]);
v.pop_front();


v.front().first

v.front()는 iterator값을 return 한다.
그 결과값에 .first 즉 pair의 첫번째 요소를 iterator를 통해
접근하면 결과 값은 first의 값을 return한다.

---

max_element

auto max = *max_element(v.begin(), v.end(), compare);

max_element 함수는 stl container의 최댓값의 iterator를 출력하는 함수이다.
그래서 *을 사용하여 iterator가 가리키는 값을 변수 max에 가져오게끔 하였다.

---

pair에서 값의 비교

bool compare(pair<int,int> a, pair<int,int> b){
    return a.first < b.first;
}

auto max = *max_element(v.begin(), v.end(), compare);

max_element 함수의 세번째 속성에 compare 함수가 들어가 있다.
이 함수는 bool 값을 return하는 함수이다.
함수의 내용을 보면 pair a와 pair b의 first 값을 비교하여 b의 값이 더 클 때 true를 리턴한다.

---

stl container 요소들의 시간복잡도

Container	찾기	node 삽입/삭제
vector	O(n)	중간 : O(n), 맨뒤 : O(1)
deque	O(n)	중간 : O(n), 앞/뒤 : amortized O(1)
list	O(n)	O(1)

---

c++ queue 의 특징

queue의 경우 iterator가 존재하지 않습니다.
그렇기 때문에 max_element가 되지 않습니다.
그렇기 때문에 queue를 사용하고 싶다면 deque를 queue처럼 사용해야 합니다.

---