Dota2의 세계에는 The Radiant와 Dire라는 두 개의 파티가 있다고 가정해 보겠습니다. Dota2 상원은 두 정당에서 온 상원의원으로 구성됩니다. 이제 상원은 Dota2 게임 내에서 몇 가지 변경 사항을 선택하려고 합니다. 이 변경에 대한 투표는 라운드 기반 절차일 수 있습니다. 각 라운드에서 각 상원의원은 다음 두 가지 권리 중 하나를 행사할 수 있습니다.
-
한 상원의원의 권리 금지 - 상원의원은 이번 라운드와 이후 라운드에서 다른 상원의원이 자신의 모든 권리를 잃게 만들 수 있습니다.
-
승리 선언 - 이 상원의원이 아직 투표권이 있는 상원 의원이 모두 동등한 정당 출신임을 발견하면 게임 내에서 승리를 선언하고 변경 사항을 선택할 수 있습니다.
각 상원의원의 정당을 나타내는 문자열이 제공됩니다. 문자 'R'과 'D'는 각각 Radiant 파티와 Dire 파티를 나타냅니다. 그런 다음 n명의 상원 의원이 있는 경우 주어진 문자열의 차원은 n이 됩니다.
라운드 기반 절차는 주 상원의원부터 지정된 순서 내에서 마지막 상원의원까지 시작됩니다. 이 절차는 투표가 끝날 때까지 지속됩니다. 권리를 상실한 모든 상원의원은 절차에서 생략됩니다.
모든 상원의원이 충분히 현명하고 자신의 정당을 위해 가장 간단한 전략을 사용할 수 있다고 가정하면, Dota2 게임 내에서 어느 정당이 최종적으로 승리를 선언하고 변경을 할 것인지 예측하고 싶습니다. 출력은 Radiant 또는 Dire여야 합니다.
따라서 입력이 "RDD"와 같으면 Dire가 됩니다. 첫 번째 상원의원은 Radiant에서 나왔고 1라운드에서 차기 상원의원의 권리를 금지할 수 있기 때문입니다. 그리고 두 번째 상원의원은 권리가 금지되어 더 이상 권리를 행사할 수 없습니다. 그 후 세 번째 상원의원은 Dire에서 와서 1라운드에서 첫 번째 상원의원의 권리를 금지할 수 있습니다. 이제 라운드 2에서 세 번째 상원의원은 상원에서 투표할 수 있는 유일한 사람이므로 승리를 발표할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
큐 q1, q2, n :=문자열 크기를 만듭니다. 모든 R의 경우 q1에 삽입하고 모든 D의 경우 q2에 삽입합니다.
-
두 대기열이 모두 비어 있지 않은 동안
-
q1의 앞 요소
-
n을 q1에 삽입하고 q2와 q1에서 삭제
-
-
그렇지 않으면 n을 q2에 삽입하고 q2와 q1에서 삭제
-
n을 1 증가
-
-
대기열이 비어 있으면 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