프로그래머스 Lv 2. 42587 c++ 프로세스

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

 

priority_queue와 queue를 이용한 코드를 작성하였다. 

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq;
    queue<pair<int,int>> q;
    for(auto c: priorities) pq.push(c);
    for(int i=0; i<priorities.size();i++) q.push({priorities[i],i});
    int t=1;
    
    while(!q.empty()){
        if(q.front().first==pq.top()){
            if(q.front().second==location)  return t;
            q.pop();
            pq.pop();
            t++;
        }else{
            pair<int,int> tmp=q.front();
            q.push(tmp);
            q.pop();
        }
    }
    return answer;
}

다른 사람의 풀이를 보니, 내가 푼것처럼 priority_queue를 이용한 풀이들도 많이 보이지만, 

*max_element()를 이용한 풀이가 굉장히 깔끔하게 구현한게 있어서 첨부해보겠다. 

 

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int max = *max_element(priorities.begin(), priorities.end());
    while (true)
    {
        for (int i = 0; i < priorities.size(); ++i)
        {
            if (priorities[i] == max)
            {
                ++answer;

                if (i == location)
                    return answer;

                priorities[i] = 0;
                max = *max_element(priorities.begin(), priorities.end());
            }
        }
    }
}

처음에 *max_element를 이용한 풀이를 떠올리긴 했으나, 계속해서 *max_element() 를 하는것이 굉장히 비효율적이게 보여서 

priority_queue를 이용한 풀이를 떠올려서 해결했는데, 로직을 구상하는데 있어서는 살짝 더 시간이 소요됐던것 같다. 

그래서 *max_element() 를 이용한 아래의 코드의 경우는 보기에도 간결해보이고 생각하기도 조금 더 쉬울것 같은 느낌이 드는데, 

효율적인 측면에서는 확실히 조금 아쉬움이 있을 코드라고 생각한다. 

두 코드 모두 주어진 `priorities` 배열에서 주어진 `location`의 문서가 출력되는데 걸리는 시간을 계산하는 것으로, 큐(Queue)와 우선순위 큐(Priority Queue)를 사용한 두 가지 방법을 제시하고 있습니다.

1. 첫 번째 코드 (Queue와 반복문 사용):
   - 시간 복잡도: 최악의 경우 O(n^2) (모든 요소가 오름차순으로 정렬된 경우)
   - `while` 루프 안에서 배열의 모든 요소를 순회하고, 최대 값을 찾기 위해 `max_element` 함수를 호출하므로 각 루프에서 O(n)의 시간이 소요됩니다. 따라서 최대 요소를 찾는 데는 O(n)의 시간이 걸린 후, 최대 값과 일치하는 요소를 찾는데 최악의 경우 O(n)의 시간이 더 소요될 수 있습니다. 최악의 경우, 반복문이 중첩되어 O(n^2)의 시간 복잡도를 가집니다.

2. 두 번째 코드 (Priority Queue와 Queue 사용):
   - 시간 복잡도: O(n * log n) (우선순위 큐를 사용하는 경우)
   - `priority_queue`를 사용하면, 우선순위가 가장 높은 요소가 항상 맨 위에 위치하므로 최대 값을 찾는 데 O(1)의 시간이 소요됩니다. 따라서 전체 반복문에서 최대 값 찾기는 O(n)이며, `priority_queue`와 `queue`를 이용하여 문서의 위치와 우선순위를 추적하므로 전체 시간 복잡도는 O(n * log n)입니다.

따라서, 두 번째 코드가 효율적인 알고리즘을 사용하여 더 빠른 시간 복잡도를 갖고 있습니다. 최악의 경우에도 O(n * log n)으로 선형 대수 시간에 가까운 성능을 보입니다.

 

두 코드의 차이에 대해서 시간복잡도 측면에서 gpt에 비교를 요구했고 그에 대한 답이다. 

이걸 참고해서 두 풀이에 대한 고려를 해본뒤에 취사선택하면 좋을것 같다. 

그래도 priority_queue가 더 좋을것 같다. 

더욱 priority_queue를 사용하는 방법에 익숙해져보도록 하자.