[프로그래머스] 프린터 / c++

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

 

[ 정답 코드 ]

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> priorities, int location){
    int answer = 0;
    queue <pair<int, int>> q;
    priority_queue <int> priq;
    
    for(int i = 0; i < priorities.size(); i++){
        q.push(make_pair(i, priorities[i]));
        // 처음 location, 중요도 push
        priq.push(priorities[i]);
        // 중요도 오름차순 정렬 push
        //priority_queue? 우선순위 큐. 자동 오름차순 정렬 기능.
    }
    
    while(!q.empty()){
        int n = q.front().first; // 맨 앞 항목 location
        int p = q.front().second; // 맨 앞 항목 중요도
        
        if(p == priq.top()){
        // 현재 항목 중요도 == 가장 중요
            if(n == location){
            // 현재 항목 == 내가 알고 싶은 위치 항목
                answer++;
                break;
            }else{
                answer++;
                q.pop();
                priq.pop();
                // 가장 중요한 항목 o, but 내가 알고 싶은 것 x, 순서 뒤로 밀림
                // 항목에 해당하는 것들 pop
            }
        }else{
            q.push(q.front());
            q.pop();
            // 항목을 뒤로 이동시킨다.
        }
    }
    
    return answer;
}

 

 

 

 

※ 틀린 이유

     (정답으로 오기 전까지)

 

① 단순 한 번 계산 문제로 생각

 

처음에는 문제 설명과 입출력 예를 보고서

단순히 가장 중요한 항목 하나를 찾으면, 그 애를 맨 앞으로 보내기 위해 나머지 항목들을 pop한뒤 뒤로 차례대로 push해 그대로 전체를 프린터해내면 되는 문제인 줄 알았다. 또한, 중요도가 같을 경우 무시하며 맨 처음으로 나온 가장 높은 중요 항목을 기준으로 뒤로 싹 밀어넣으면 되는 줄 알았다!

 

queue 문제지만 단순 수학 공식으로 풀 수 있다 생각해 이런 식으로 코드를 짰었다.

 

답 = (현재위치+1) - pop한 갯수 (count++)
if(답<0){
     답+priorities.길이;
}

 

 

[ 첫 번째 틀린 코드 ]

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int max = 0;
    int count = 0;
    
    for(int i=0; i<priorities.size(); i++){
        if(priorities[i] > max){
            max = i;
        }
    }
    
    for(int j=max; j>0; j--){
        count++;
    }
    
    int A = (location+1)-count;
    
    if(A>=0){
        answer = A;
    }else{
        answer = A + priorities.size();
    }
    
    return answer;
}

 

그런데 한번 pop해낼 때마다 새롭게 다시 재배열을 해서 프린트를 하는 문제였어서 다시 풀었다.

 

 

 

② queue에서는 q[i]를 쓸 수 없음.

 

queue에서 쓸 수 있는 함수는?

push(), pop()

front(), back()

empty(), size()

 

하지만 FIFO queue 특성상 중간의 인자들은 맘껏 확인할 수 없다.

 

 

[ 두번 째 틀린 코드 ]

 

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue <int> q;
    int max = 0;
    int A = 1;
    
    for(int i=0; i<priorities.size(); i++){
        q.push(priorities[i]);
    }
    
    while(q.size()>0){
        for(int i=0; i<q.size(); i++){
            if(q[i] > max){
                max = i;
            }
        }
        
        for(int j=max; j>0; j--){
            int n = q.front();
            q.pop();
            q.push(n);
        }
        
        q.pop();
        
        if(max == location){
            A = answer;
        }else{
            A++;
        }
        
    }
    
    return answer;
}

 

 

그래서 vector로 priorities[i]를 이용한 다음

priorities.erase(max); 를 하려고 했지만, 그렇게 되려면 vector에서도 pop(), push()를 해 queue와 같이 재정렬해줘야하는데

vector는 뒤에서만 넣고 뺄 수 있다보니 그것도 되지 않았다.

 

생각해보니 결국 중간에 생각했던 pair를 이용해 풀 수 밖에 없다고 판단하여 성공하였다.

 

 

 

* 오늘의 교훈

많은 것을 배웠지만, queue의 특성을 알고 처음부터 안된다는 것을 알면 뻘짓을 안하고 훨씬 더 빨리 풀 수 있다.

기본적인 특성을 알고 시작하자!