Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 큐(Queue)로 해결하는 Dota2 상원 승리 예측 문제

Dota2 세계에는 라디언트(Radiant)와 다이어(Dire)라는 두 진영이 존재합니다. Dota2 상원은 두 진영 출신 의원들로 구성되어 있으며, 게임 변경 사항에 대한 결정을 내리기 위해 투표를 진행합니다.

문제 개요

투표는 라운드 기반 절차로 진행됩니다. 각 라운드마다 의원은 다음 두 가지 권리 중 하나를 행사할 수 있습니다.

  • 권리 박탈 − 한 의원은 다른 의원의 권리를 박탈하여, 해당 의원이 이번 라운드와 이후 모든 라운드에서 투표권을 잃게 만들 수 있습니다.

  • 승리 선언 − 만약 어떤 의원이 아직 투표권을 가진 의원들이 모두 같은 진영 소속임을 확인하면, 승리를 선언하고 게임 변경에 대한 결정을 내릴 수 있습니다.

각 의원의 소속 진영을 나타내는 문자열이 주어집니다. 문자 'R'과 'D'는 각각 라디언트 진영과 다이어 진영을 의미합니다. 의원이 n명이라면 주어진 문자열의 길이 역시 n입니다.

투표 절차는 주어진 순서대로 첫 번째 의원부터 시작하여 마지막 의원까지 진행됩니다. 이 절차는 투표가 종료될 때까지 반복되며, 권리를 잃은 의원들은 절차 도중 건너뛰어집니다.

모든 의원은 자신의 진영을 위해 최선의 전략을 구사할 만큼 현명하다고 가정할 때, 최종적으로 어느 진영이 승리를 선언하고 게임 변경을 결정하게 될지 예측해야 합니다. 출력값은 Radiant 또는 Dire여야 합니다.

예시 이해하기

입력이 "RDD"라면 결과는 Dire입니다. 그 과정은 다음과 같습니다.

  1. 첫 번째 의원은 라디언트 소속으로, 1라운드에서 곧바로 다음 의원의 권리를 박탈합니다.
  2. 두 번째 의원은 권리가 박탈되어 더 이상 어떤 권리도 행사할 수 없습니다.
  3. 세 번째 의원은 다이어 소속으로, 1라운드에서 첫 번째 의원의 권리를 박탈합니다.
  4. 2라운드에서 세 번째 의원은 상원에서 유일하게 투표권을 가진 인물이므로 승리를 선언할 수 있습니다.

접근 방법: 큐(Queue) 활용

이 문제는 두 개의 큐를 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 의원이 자신의 차례가 되었을 때 가장 먼저 투표할 상대 진영 의원을 박탈하는 것입니다. 인덱스를 큐에 저장하면 라운드가 반복되어도 투표 순서를 자연스럽게 시뮬레이션할 수 있습니다.

해결 절차는 다음과 같습니다.

  • 두 개의 큐 q1, q2를 생성하고, n := 문자열의 길이로 초기화합니다. 문자열을 순회하며 'R'이면 해당 인덱스를 q1에, 'D'면 q2에 삽입합니다.
  • 두 큐가 모두 비어 있지 않은 동안 다음을 반복합니다.
    • q1의 front 값이 q2의 front 값보다 작으면, 라디언트 의원이 먼저 행동하므로 n을 q1에 삽입하고 q2와 q1에서 각각 pop 합니다. (라디언트가 다이어 의원을 박탈)
    • 그렇지 않으면 n을 q2에 삽입하고 q2와 q1에서 각각 pop 합니다. (다이어가 라디언트 의원을 박탈)
    • n을 1 증가시킵니다.
  • 반복이 끝난 후 q1이 비어 있으면 "Dire"를 반환하고, 그렇지 않으면 "Radiant"를 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string predictPartyVictory(string s) {
        queue <int> q1, q2;
        int n = s.size();
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'R'){
                q1.push(i);
            } else {
                q2.push(i);
            }
        }
        while(q1.size() && q2.size()){
            if(q1.front() < q2.front()){
                q1.push(n);
                q2.pop();
                q1.pop();
            } else {
                q2.push(n);
                q2.pop();
                q1.pop();
            }
            n++;
        }
        return q1.empty()? "Dire" : "Radiant";
    }
};
main(){
    Solution ob;
    cout <<(ob.predictPartyVictory("RDD"));
}

입력

"RDD"

출력

Dire

마무리

이 문제는 탐욕(Greedy) 전략과 큐 자료구조를 결합한 대표적인 시뮬레이션 문제입니다. 각 의원이 자신보다 앞선 위치의 적대 진영 의원을 우선적으로 박탈한다는 규칙만 지키면, 생존한 의원의 인덱스를 큐 뒤에 다시 삽입하는 방식으로 여러 라운드를 손쉽게 처리할 수 있습니다. 매 반복마다 정확히 한 명의 의원이 제거되므로 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.