[고득점Kit][큐] 프린터 ⭐⭐

[스택/큐] 프린터

난이도 ⭐⭐

문제

내 풀이

프로그래머스 고득점 Kit의 스택/큐 마지막 문제.. 어느정도 연습이 잘 됐나보다. 실패 없이 한방에 통과 ^ㅁ^

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

using namespace std;

bool compare(const int & a, const int & b)
{
    return a > b;  // 내림차순 정렬
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    queue<int> print; 
    queue<pair<int, int>>  waiting; // 인덱스, 우선 순위
    queue<int> sorted;
    
    /* waiting 큐에 <인덱스, 우선순위> 쌍 삽입 */
    for(int i = 0; i < priorities.size(); i++)
    {
        waiting.push(make_pair(i, priorities[i]));
    }
    
    /* 우선순위 벡터를 내림차순 정렬 후 sorted 큐에 삽입 */
    sort(priorities.begin(), priorities.end(), compare);
    for(int i = 0; i < priorities.size(); i++)
    {
        sorted.push(priorities[i]);
    }
    
    
    while(!waiting.empty())
    {
        /* sorted 큐는 내림차순 정렬되어있으므로 맨 앞 front() 원소는 최대값이다. */

        /* 대기 큐의 맨 앞 원소의 우선순위(second)가 우선순위 최대값보다 작다면 */
        if (waiting.front().second < sorted.front())
        {
            waiting.push(waiting.front());  // 대기 큐의 맨 뒤에 삽입 후 
            waiting.pop();                   // 맨 앞은 제거. 즉 맨 앞에 있던걸 뒤에 줄서게 한 것. 나보다 더 빨리 프린트 되야할게 있다는 거니까!
        }
        /* 내가 현재 최대 우선순위였다면 프린트해야함! */
        else
        {
            print.push(waiting.front().first);  // 출력 큐에 인덱스(first)를 삽입
            waiting.pop();                      // 대기 큐에선 삭제
            sorted.pop();                       // 정렬 큐에서도 삭제해주기
        }
    }
    
    /* 최종적인 출력 순서가 되는 인덱스가 모인 print큐에서 location과 일치하는 인덱스 찾기 */
    while(true)
    {
        answer++;    // 마치 count 
        if (location == print.front())
            break;
        else
            print.pop();
    }
    
    return answer;
}

• 큐를 3 개 두었다.
  • 💡 sorted 큐
    • 우선순위 값이 담겨 있는 priorities 벡터 원소들을 내림 차순으로 정렬한 후 sorted 큐에 전부 삽입해준다.
    • 우선순위 값들이 내림차순 정렬된 <int> 큐
  • 💡 waiting 큐
    • 대기 열이 될 큐.
    • sorted 큐에 정렬된대로 삽입하기 위해 priorities 벡터를 정렬했었는데 정렬 전의 인덱스 또한 기억해주기 위하여 <pair<int, int> 형태의 큐로 정의했다.
      • (원래 인덱스, 우선순위)
  • 💡 print 큐
    • 최종적인 출력 순서가 될 큐
    • 인덱스만 들어갈 <int> 타입의 큐 이다.
• 예시
  • 시작
    • waiting 큐 [(0, 2), (1, 1), (2, 3), (3, 2)]
    • sorted 큐 [3, 2, 2, 1]
    • print 큐 []

다른 풀이

대기 인덱스, 최종 출력 순서가 될 인덱스 이렇게 각각 들어갈 큐 2개를 두고 대기 인덱스 큐의 원소 값으로 priorities[원소] 이런식으로 접근한 후 *max_element(priorities.begin(),priorities.end()) 와 비교하여 대기 인덱스 push/pop 한 다른 분의 풀이도 있었다. 이 풀이 좋은 것 같다.. 나처럼 굳이 큐를 3개 둘 필요는 없었던 것 같다. 사실 인덱스만 다뤄도 되고 !

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기