[프로그래머스] 프린터 - 스택/큐, max_element, min_element

문제

 

풀이

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> q;
    int index = location, j, next, count = 0;
    bool en_pop = true;
    
    for(int pri : priorities){
        q.push(pri);
    }
    
    while(1){
        en_pop = true;
        j = q.front();
        q.pop();
        if(q.empty()){
            count++; 
            break;
        }
        int size = q.size();
        for (int i=0; i<size; i++){
            next = q.front();
            q.pop();
            if(next > j) en_pop = false;
            q.push(next);
        }
        
        if(!en_pop){ // 더 높은 우선순위가 있음
            q.push(j);
            if(index == 0) 
                index = q.size() -1;
            else 
                index--;
        }
        else { // 더 낮은 우선순위가 있음
            count++;
            if(index == 0) 
                break;
            else 
                index--;
        }
    }
    return  count;
}

 

변수 설명

• en_pop : 현재 J보다 우선순위가 높은 문서가 없어 pop이 가능한지를 확인하기 위한 변수
• index : 내가 요청한 문서의 현재 위치
• next : J가 아닌 다른 문서. J보다 우선순위가 높은지 확인하기 위한 변수 

 

해결방법.

1. J를 꺼낸다.
2. queue를 전부 돌면서 J와 우선순위를 비교한다. 
3. J보다 우선순위가 높은 문서가 있다면(en_pop = false), J를 다시 queue에 push 하고, index를 -1 해준다.
4. J보다 우선순위가 높은 문서가 없다면(en_pop = true), J를 push하지않고 count +1 해준다. index -1 해준다.
5. J가 index였다면(내가 요청한 문서) 반복문을 빠져나온다.

아주 복잡한 해결방법이 되었다...

 

---

 

다른 사람 풀이

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

using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> printer;                         //queue에 index 삽입.
    vector<int> sorted;                         //정렬된 결과 저장용
    for(int i=0; i<priorities.size(); i++) {
        printer.push(i);
    }
    while(!printer.empty()) {
        int now_index = printer.front();
        printer.pop();
        if(priorities[now_index] != *max_element(priorities.begin(),priorities.end())) {
            //아닌경우 push
            printer.push(now_index);
        } else {
            //맞는경우
            sorted.push_back(now_index);
            priorities[now_index] = 0;
        }
    }
    for(int i=0; i<sorted.size(); i++) {
        if(sorted[i] == location) return i+1;
    }
}

 

max_element를 통해 vector의 최댓값을 한 줄로 알 수 있다!

우선순위가 가장 높은 문서의 index를 순서대로 vector에 넣어놓아, location문서가 언제 pop 되었는지 알아내었다.

 

이 알고리즘을 짜낸 사람은 정말 천재가 아닐까..

본받자.. 내가되자...

 

 

max_element 와 min_element

• for문을 작성하지 않고 최댓값, 최솟값을 구할 수 있고, index도 알 수 있다.
• algorithm 라이브러리에 있는 함수이다.

//가장 큰 수를 반환
*max_element(v.begin(), v.end())
// 가장 큰 수의 인덱스 반환
max_element(v.begin(), v.end()) - v.begin() 

//가장 작은 수를 반환
*min_element(v.begin(), v.end());
// 가장 작은 수의 인덱스 반환
min_element(v.begin(), v.end()) - v.begin()

---

https://notepad96.tistory.com/40

C++ Vector 최대값, 최소값, 인덱스 구하기