[C++] 프로그래머스 프린터

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

코딩테스트 연습 - 프린터

 

1. 서론

 

'프린터' '순서' '인쇄 요청' '우선순위' => 큐로 푸는 문제

 

2. 문제 풀이 

 

이 문제의 핵심은 이 과정을 통해 답을 도출하는 것이다. 

 

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

3. 그렇지 않으면 J를 인쇄합니다.

 

스택/큐 카테고리에 있었지만 오기로 벡터로 풀었다가 55점 맞고 큐로 고쳤다. (아직도 뭐가 문제인지 잘 모르겠음... 반례를 못 찾아서)

처음에는 그냥 1,2,3을 그대로 하기보다는 결과론적으로 생각했다. 정렬이 되어야 하고, 정렬 후에 location을 찾아 return 값 받기에 매몰되어 있었다고나 할까...

 

1,2,3번을 큐로 구현했다. 그러기 위해서 큐를 세 개나 썼다. 조금 낭비 같기는 한데 이외에는 딱히 방법이 떠오르지 않아서 ㅎ...

1번 큐는 원래 정렬 전의 기본 값을 가지고 있다.

2번 큐는 1번 큐를 복사한 후 첫 번째 항을 따로 빼서 나머지 값과 비교해 우선순위 값이 더 높은 경우를 찾을 때까지 pop 하면서 한 바퀴 돈다. 이 경우에 위의 2번을 행하는데 중요도가 높은 문서가 있으면 1번 큐에 맨 뒤에 값을 넣고, 맨 앞 값은 pop 해준다.

1번 큐와 2번 큐를 이용해 정렬을 할 경우, 가장 앞의 항에 가장 우선순위가 높은 값이 오게 된다. 

하지만 맹점이 있다면 높은 게 맨 앞으로 오더라도 그저 뒤에 나머지 값을 순서 없이 넣어줬기 때문에 그 부분에 대한 정렬도 필요하다.

그래서 3번 큐를 사용했다.

3번 큐에는 1번 큐에서 맨 앞 항이 나머지 항들보다 우선순위가 높으면 값을 넣어주게 해줬다. 넣은 값은 1번큐에서 pop 하고 나머지 항들은 다시 위와 같은 작업을 반복해줘서 정렬을 마친다.

 

진짜 복잡하게 풀었다... 이렇게 하는 게 맞다고? 싶을 정도. 뭔가 반례가 있을 것 같은데 맞아서 다행이다...

 

스케치

 

 

3. 코드 설명

 

#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0, i, a, b, f = 0;
    queue<pair<int, int>> q, t, x;
    
    for (i = 0; i < priorities.size(); i++)
        q.push(make_pair(i , priorities[i]));
    
    while(!q.empty())
    {
        t = q;
        a = t.front().first;
        b = t.front().second;
        t.pop();
        f = 0;
        
        for (i = 0; i < t.size(); i++)
        {
            if(b < t.front().second)
            {
                q.push(make_pair(a, b)); 
                q.pop();
                f = 1;
                break;
            }
            else
            {
                t.pop();
                i = 0;
            }
        }  
        
        if(f != 1)
        {
            x.push(make_pair(q.front().first, q.front().second));
            q.pop();
        }
       
    }
 
    while(!x.empty())
    {
        answer++;
        
        if (x.front().first == location)
            break;

        x.pop();
    }

    return answer;
}

 

 

이렇게 푼 인간도 있구나 하고 봐주십시오

 

큐를 pair로 만들어서 풀었는데 첫 번째 항에는 맨 처음의 index 값, 두 번째 항에는 우선순위 값을 넣는다.

그리고 정렬을 하기 위해 반복문을 돌린다.

a, b는 맨 앞 항의 값을 저장하는 변수다. t는 큐 특성상 배열처럼 순회가 안되기 때문에 pop을 하며 항목을 보기 위해 임시로 만든 큐다. 반복문이 돌 때마다 다시 원래의 q값을 받아 사용한다.

f는 정렬이 다 됐는지 판단해주는 변수다. f의 값이 변한 경우는 if문 안에 들어갔을 경우인데 if문 안에 들어간 경우는 우선순위가 높은 게 아직 남았다는 뜻이고, 들어가지 않았다는 건 우선순위가 높은게 없다는 뜻이기 때문에 f가 1이 아닌 경우는 정렬이 끝났다고 간주한다.

그 후에 확정된 값만 x큐에 넣고 다시 위와 같은 과정을 거치며 x에 모든 값이 들어가면 q는 전부 pop이 되었기 때문에 반복문이 끝난다.

 

내가 생각해서 푼 거지만 어떻게 이런 생각을 해서 풀었지? 싶다. 짧은 시간 안에 풀기엔 부적절한 방법일지도