프로그래머스 - 프로세스 - C++

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

프로그래머스

 

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

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int maxId=0;
    vector<bool> b(priorities.size(),0);
    // 반복해서 startIdx 와 location이 같으면 종료
    while(true)
    {
        // 가장 큰 수를 찾아서 maxIdx 로 세팅
        for(int i=maxId,cnt=0;cnt<priorities.size();i=(i+1)%priorities.size(),cnt++)
        {
            if(b[i]==false && priorities[maxId]<priorities[i])
                maxId=i;
        }
        // cnt 1 증가시키기 
        answer++;
        b[maxId]=true;
        if(maxId==location)
            break;
        maxId = (maxId+1)%priorities.size();
        while(b[maxId])
            maxId = (maxId+1)%priorities.size();
    }
    
    return answer;
}

 

다음 코드는 인덱스를 이용해서 for문을 돌 시작위치를 계속 갱신하는 것으로 큐를 대체했다. 

maxId는 큐의 제일 앞쪽의 원소라고 생각한다. 

 

1. maxId 부터 시작하여 모든 큐를 보며 제일 큰 수의 인덱스를 찾는다. 

answer를 1 증가시키고 maxId를 갱신한다. 

이 때, vector자료구조를 그대로 사용하기 때문에 실행된 인덱스가 빠지지않아서 bool 벡터로 표시했다. 

다음 maxId를 구하고 그 수부터 가장 큰 값을 찾기위해 다시 반복한다. 

만약 maxId 가 알고싶은 location이라면 answer를 리턴한다. 

 

삽입,삭제나 다른 자료구조의 사용등을 하지않고 최대한 효율적으로 작성하기 위해 방법을 떠올렸지만

결국 O(n^2)의 시간복잡도를 가지게 되었다. 

 

여기서 우선순위큐를 사용하면 O(n(logN))의 시간복잡도를 가지기 때문에 위와 같은 방법은 비효율적인 것으로 보인다. 

앞으로도 더 공부하여 검증된 더 효율적인 방법들을 익혀야겠다. 

 

다음은 우선순위큐를 이용한 코드이다. 

#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> pq;
    
    for(int i=0;i<priorities.size();i++)
    {
        q.push({i,priorities[i]});
        pq.push(priorities[i]);
    }
    
    while(!q.empty())
    {
        int idx = q.front().first;
        int pri = q.front().second;
        q.pop();
        if(pri == pq.top())
        {
            answer++;
            if(location==idx)
                return answer;
            pq.pop();
            
        }
        else
            q.push({idx,pri});
    }
    
    return answer;
}

 

큐를 이용해 {인덱스, 우선순위를}를 묶어서 다시 저장하고

우선순위큐를 이용해 우선순위를 저장한다. 

저장할 때, 자동으로 우선순위가 높은 순으로 저장된다. 

그리고 큐가 빌 때까지 반복하며 앞에서부터 꺼내 우선순위큐에서 가장높은것과 비교해 가장 높으면 location과 비교해 처리한다. 

아니라면 큐를 다시 넣고 반복한다.

stl을 쓰는게 코드 작성할때도 훨씬 깔끔한 것 같다.

 

두 코드를 chatgpt에게 천개의 테스트케이스를 통해서 어떤게 더 효율적인지 분석해달라한 결과이다. 

queue-based가 위의 코드이고 priority queue-based가 아래 우선순위를 이용한 코드이다. 

보는 바와 같이 약 9배정도의 속도차이가 있으며 시간복잡도도 n^2 과 nlogN 의 차이가 있다. 

이런 문제에선 바로 우선순위큐를 사용하는 것이 훨씬 효율적이라는 결론을 낼 수 있다.