[Programmers]#Level3_숫자 게임, 우선순위 큐, 스택

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. 우선순위 큐

[자료구조]#7_우선순위 큐

우선순위 큐는 힙의 한 종류로, 각 항목이 우선순위에 따라 정렬된 연결 자료구조입니다. 우선순위 큐는 원소의 삽입 순서와 무관하게 우선순위가 가장 높은 항목이 먼저 제거되는 특징을 갖고 있습니다. 더불어, 우선순위 큐의 각 원소는 우선순위에 따라 반 정렬된 상태를 유지합니다. 일반적으로, 우선순위 큐는 힙 자료구조를 통해 구현하며, 삽입/삭제 작업의 최악 시간 복잡도는 O(log n)입니다. 

 

2. 스택

[자료 구조]#0_선형 자료구조

스택은 후입 선출 방식으로 동작하는 선형 자료구조입니다. 스택은 동일한 유형의 데이터 항목을 데이터 목록의 한쪽 끝에서만 삽입/삭제하는 특징을 갖고 있습니다.

 

3. A팀의 최대 값과 B팀의 최대 값 비교, 남은건 stack에 넣자!

1. 먼저, 두 개의 우선순위 큐를 선언하고, 각각 A팀의 점수와 B팀의 점수를 삽입합니다.
2. A팀의 최고점과 B팀의 최고점을 비교하고, B팀의 최고점이 더 크다면 해당 값을 우선순위 큐에서 제거하고, stack에 삽입합니다.
3. 다시, A팀의 최고점과 스택의 첫 번째 값을 비교하여, 스택의 첫 번째 값이 더 크다면 승점 획득으로 처리합니다.
4. 위 과정을 반복하고, 최종적으로 B팀이 얻을 수 있는 승점을 반환해 줍니다.

 

---

 

#3. 코드

/*
    @문제 : A팀 자연수 목록을 보고, B팀이 출전 선수 순서를 변경하여 얻을 수 있는 최대 승점
    @설명
        1. A팀 원소와 B팀 원소를 담을 두 개의 우선순위 큐
        2. A팀 가장 큰 원소보다 큰 B팀의 원소는 우선 stack에 넣는다.
        3. A팀 가장 큰 원소보다 작은 B팀의 원소를 찾으면, A팀의 원소를 stack.top()과 비교
        4. 이때, stack의 top이 A팀의 가장 큰 원소보다 크다면! 승점 획득!
        5. 반면, stack의 top이 A팀의 가장 큰 원소보다 작다면! 더 이상 이길 수 없으므로 끝!
*/

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

using namespace std;

int solution(vector<int> A, vector<int> B) {

    int ans = 0;
    // #1. pq 2개?
    priority_queue<int, vector<int>> pqA;
    priority_queue<int, vector<int>> pqB;
    stack<int> s;

    // #2. pq 초기화
    for(int i=0; i<(int)A.size();++i)
    {
        pqA.push(A[i]);
        pqB.push(B[i]);
    }

    // #3. 이기는 조건 확인
    while(!pqA.empty())
    {
        int curA = pqA.top();
        pqA.pop();

        // 1. pqA.top()과 pqB.top() 비교, pqA.top()이 pqB.top() 보다 클 때까지 stack에 pqB.top() 넣고, pqB.pop() 수행
        while(!pqB.empty() && curA < pqB.top())
        {
            s.push(pqB.top());
            pqB.pop();
        }
        // 2.stack이 비어있지 않다면?
        if(!s.empty())
        {
            // 3. pqA.top()과 s.top() 비교, s.top()이 pqA.top()보다 크다면, 승점 획득!
            if(s.top() > curA)
            {
                ans++;
                s.pop();
            }
            // 4. pqA.top()과 s.top() 비교, s.top()이 pqA.top()보다 작다면, 끝! 더이상 B팀은 A팀을 이길 원소가 없다
            else break;
        }
    }

    return ans;
}

 

---