프로그래머스 문제 풀이 프린터

문제 URL 프린터

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

먼저 문제에 따르면, priorities에는 문서의 중요도별로 존재합니다. 이 때 location에 위치한 문서가 출력 순서가 어떻게 되는지 반환하면 되는 문제입니다. 어느 때와 마찬가지로 입력을 예제로 직관적으로 문제를 풀어봅시다. 첫 번째 입력입니다.

 

priorities : [2, 1, 3, 2]
location : 2

 

priorities를 인덱스별로 나타내면 다음과 같습니다.

 

priorities : [2, 1, 3, 2]
index :     [0, 1, 2, 3]
location : 2

 

우리는 index가 location, 즉 2인 문서를 뽑아내면 됩니다. 문제에 따르면, prorities에서 출력될 문서들은 자신보다 중요도가 높은 문서가 있으면, 순서 맨 뒤로 가게 됩니다.

 

따라서 현재 가장 맨 앞의 문서 priority=2, index=0인 문서는 가장 맨 뒤로 갑니다.

 

front : (priority=2, index=0)
priorities : [1, 3, 2, 2]
index :     [1, 2, 3, 0]
location : 2

 

이제 맨 앞의 문서는 priority=1, index=1인 녀석이 됩니다. 그러나 역시 prorities 안에 중요도가 높은 문서가 존재하므로, 맨 뒤로 갑니다.

 

front : (priority=1, index=1)
priorities : [3, 2, 2, 1]
index :     [2, 3, 0, 1]
location : 2

 

이제 맨 앞의 문서는 priority=3, index=2인 녀석입니다. priorities 중 자신보다 높은 중요도를 가지고 있는 문서는 존재하지 않습니다. 따라서, 이 문서를 출력하면 됩니다.

 

이 때 이 문서를 출력했을 때, 출력 횟수는 1이 됩니다. 또한, location과 idx가 일치하므로, 이 문제의 입력에 따른 답은 1이 됩니다. 어떻게 동작하는지 아시겠나요?

 

이 문제에서 "중요도"를 빼면, 선입 선출 구조로 문서가 출력된다는 것을 알 수 있습니다. 따라서 큐를 통해서 문제를 풀수 있다는 것이죠. 이번엔 큐를 이용해서 문제를 풀어봅시다. 먼저, (idx, priority) 쌍으로 저장되는 큐를 생성합니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 0 //출력 횟수
q : [ (0, 2), (1, 1), (2, 3), (3, 4) ] // (idx, proirity) 쌍으로 저장하는 큐

 

이제 큐가 비거나, location에 해당하는 문서가 출력될때까지 문서를 출력해봅시다. 먼저 처음 저장된 문서를 빼옵니다.

 

priorities : [2, 1, 3, 2]
location : 2
front : (0, 2) //빼온 문서
q : [ (1, 1), (2, 3), (3, 4) ] //문서 하나가 빠짐.

 

이 때 빼온 문서 front의 중요도보다 높은 중요도를 가진 문서가 큐에 있는지 확인합니다. (idx=2, priority=3)인 문서가 있네요. 그러면, 다시 q에 저장합니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 0
front : (0, 2)
q : [ (1, 1), (2, 3), (3, 4), (0, 2) ] //다시 들어옴.

 

다시, q에서 첫 번째 문서를 빼옵니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 0
front : (1, 1) //빼온 문서
q : [ (2, 3), (3, 4), (0, 2) ] //문서 하나가 빠짐

 

역시 front보다 중요도가 높은 문서가 q속에 존재합니다. 다시 q에 넣습니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 0
front : (1, 1)
q : [ (2, 3), (3, 4), (0, 2), (1, 1) ] //다시 들어옴

 

다시, q에서 첫 번째 문서를 빼옵니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 0
front : (2, 3) // 빼온 문서
q : [ (3, 4), (0, 2), (1, 1) ] //문서 하나가 빠짐

 

현재 문서 front보다 중요도가 높은 문서는 q속에 없습니다. 따라서, 이 문서를 출력합니다.

 

priorities : [2, 1, 3, 2]
location : 2
answer : 1 //출력해서 1올라감.
front : (2, 3)
q : [ (3, 4), (0, 2), (1, 1) ]

 

근데 현재 출력된 문서의 idx가 location의 값인 2로 일치합니다. 이 경우, 출력을 멈추가 정답을 반환하면 됩니다. 어떻게 동작하는지 보이시나요? 이제 코드를 통해서 알아봅시다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. (idx, priority) 형태로 문서를 저장한 q를 생성합니다.
2. q가 비거나, location에 해당하는 문서를 출력할 때까지, 다음을 반복합니다.
   1. 가장 맨 앞의 문서 front를 q에서 가져옵니다.
   2. front와 q에 저장된 문서들의 중요도를 비교합니다.
      1. 만약 높은 것이 있다면, front는 다시 q에 저장합니다.
      2. 없다면, front를 출력합니다.
         1. 출력 횟수를 1 올립니다.
         2. 출력된 문서의 idx와 location이 일치한다면, 반복을 멈추고 답을 반환합니다.

아래 코드들은 알고리즘을 코드로 나타낸 것입니다. 비교해서 살펴보시면 이해가 빠를겁니다. 다음은 파이썬 코드입니다.

 

PYTHON 코드

def solution(priorities, location):
    # 1. (idx, priority) 형태로 문서를 저장한 q를 생성합니다.
    q = [ (idx, priority) for (idx, priority) in enumerate(priorities) ]
    answer = 0
    
    # 2. q가 비거나, location에 해당하는 문서를 출력할 때까지, 다음을 반복합니다.
    while q:
        # 1. 가장 맨 앞의 문서 front를 q에서 가져옵니다.
        front = q.pop(0)
        
        # 2. 큐속에 저장된 문서들과 현재 문서 front의 우선 순위를 비교합니다. 
        # 2-1. 큐 속에 저장된 문서 중, 자신보다 우선 순위가 높은 것이 있다면, 다시 큐 속에 저장됩니다.
        # 2-2. 높은 것이 없다면, 출력합니다.
        # 2-2-1. 출력 answer += 1
        # 2-2-2. 만약 location에 해당하는 문서라면, 반복을 멈춥니다.
        if any( front[1] < doc[1] for doc in q ):
            q.append(front)
        else:
            answer += 1
            
            if front[0] == location:
                break
            
    return answer


if __name__ == '__main__':
    priorities = [2, 1, 3, 2]
    location = 2
    result = solution(priorities, location)
    print(result)

 

이번엔 CPP 코드입니다. CPP의 경우, queue 안에 중요도가 높은 문서가 있는지 확인하기 어렵습니다.

 

물론 vector를 이용하면, algorithm 헤더에 max_element를 이용해서 파이썬과 유사한 코드를 만들 수 있습니다. 그러나 저는 권장하지 않습니다. 왜냐하면 제가 생각하기에 vector를 큐처럼 사용했을 경우 가독성이 많이 떨어진다고 생각하기 때문입니다. 

 

그래서, q에 저장된 문서들 중 현재 문서보다 중요가 높은 것이 있는지 알아내기 위해서 임시 큐 하나를 더 만들어서, 큐 안에 데이터를 확인하도록 하겠습니다.

 

기본 뼈대는 비슷하기 때문에, 알고리즘 순서만 간단히 나타내도록 하겠습니다.

 

1. (idx, priority) 형태로 문서를 저장한 q를 생성합니다.
2. q가 비거나, location에 해당하는 문서를 출력할 때까지, 다음을 반복합니다.
   1. 가장 맨 앞의 문서 front를 q에서 가져옵니다.
   2. front와 q에 저장된 문서들의 중요도를 비교합니다.
      1. 임시 큐 tmp를 만듭니다.
      2. q 속에 저장된 문서들의 중요도가 현재의 문서의 중요도보다 높은 것이 나타날때까지 q에서 문서를 빼 tmp에 넣습니다.
      3. q가 비어있는지 확인합니다.
         1. q가 비어 있지 않다면, front를 다시 q에 넣습니다.
         2. q가 비어 있다면, 다음을 실행합니다.
            1. 출력 횟수를 1 올립니다.
            2. 출력된 문서의 idx와 location이 일치한다면, 반복을 멈추고 답을 반환합니다.
      4. tmp의 저장된 문서들을 다시 q에 저장합니다.

이 알고리즘을 토대로 만든 CPP 코드는 다음과 같습니다. 파이썬과 비교해보면, 파이썬이 얼마나 간단 명료하게 코드를 나타낼 수 있는지 더 느낌이 잘 올 것 같네요.

 

CPP 코드

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

#include <iostream>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    bool isExist = false;
    // 1. ( idx, priority ) 형태로 문서를 저장하는 q를 생성합니다.
    queue<pair<int, int>> q;

    for (int i=0; i<priorities.size(); i++) {
        q.push({i, priorities[i]});
    }
    
    // 2. q가 완전히 비거나, location에 해당하는 문서를 출력할 때까지 다음을 반복합니다.
    while (!q.empty() && !isExist) {
        // 1. 임시 큐 tmp를 생성합니다.
        queue<pair<int, int>> tmp;
        // 2. q에서 가장 맨앞의 문서를 가져옵니다.
        auto front = q.front();
        q.pop();
        
        // 3. 임시 큐를 활용해, 현재 문서보다 중요도가 높은 문서가 있는지 확인합니다.
        // 3-1. 큐 속에 저장된 문서의 중요도가 현재 문서의 중요도보다 높은 것이 나타날때까지, tmp에 q데이터를 넣습니다
        while (!q.empty() && q.front().second <= front.second) {
            tmp.push(q.front());
            q.pop();
        }
        // 3-2. 먄약 큐가 비지 않았다면, 현재 문서보다 중요도가 높은 문서가 존재하는 것입니다. 따라서, 다시 front를 큐에 넣습니다.
        if (!q.empty()) {
            q.push(front);
        } else {
            // 비었다면, 문서를 출력합니다. 만약 lcoation과 문서의 idx가 같다면, 반복을 멈춥니다.
            answer += 1;
            isExist = (location == front.first);
        }
        
        // 3-3. 임시 큐에 저장된 문서들들 다시 q로 돌려 놓습니다. 
        while (!tmp.empty()) {  
            q.push(tmp.front());
            tmp.pop();
        } 
    }
    
    return answer;
}

int main() {
    vector<int> priorities = {2, 1, 3, 2};
    int location = 2;
    auto result = solution(priorities, location);
    cout << result << endl;
}