23.05.04. 풀었던 문제들

Leetcode 649. Dota2 Senate

 Greedy + Queue를 사용하는 문제. 2개의 종류 R, D가 있을 때 이 문제는 앞에서부터 선택권을 가지기 때문에, 자신보다 뒤에 있는 다른 종류의 char를 없애는 것이 제일 optimal한 선택이다.

 예를 들어 RD가 있다고 하자. 만약 D의 차례에서 자신보다 앞에 있는 R의 char를 없애는 것을 optimal이라 하자. 그러나 순서는 R부터이기 때문에 R은 D를 지울 수 있다. 따라서 이건 optimal이 아니므로 - 자신보다 뒤에 있는 다른 종류의 char를 지우는 것이 제일 optimal이다. (greedy)

 자신보다 뒤에 있는 다른 type의 char를 없애는 것을 반복한다면 다시 처음부터 시작하게 되는데, 결국 환형을 이루게 된다. - 즉 queue로 풀 수 있다는 것. 

 그러나 queue 1개만으로 풀기는 쉽지 않은 문제이다. 어떻게 count를 잘 두어서 자신보다 뒤에 오는 다른 종류의 char를 하나 없앤다고 해도, 언제 이 탐색을 종료할 수 있을지가... 매 탐색에서 queue에 모두 같은 char가 있는지 탐색하는 건 아니지 않나? 더 좋은 방법이 있을 것이다.

 

 해법은 queue 2개를 사용하는 것이다. 각각 R, D들의 index에 대한 queue를 두고, front index를 비교한다. 더 큰 쪽은 더 작은 쪽에 의해 사라지는 것이 greedy optimal이기 때문에 index가 더 적은 쪽을 살려서 queue에 넣는다.(더 큰 큰쪽은 넣지 않는다) 단, 넣을 때 환형이 되는 것을 고려해 n을 더해 주어야 할 것이다.

// Runtime 9 ms Beats 48.47%
// Memory 8.1 MB Beats 37.2%


class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.length();
        queue<int> rq, dq; // queue 2개
        for(int i = 0 ; i<senate.length(); i++){
            if(senate[i] == 'R') rq.push(i);
            else dq.push(i);
        }

        while(!rq.empty() && !dq.empty()){
            int rqFrontIdx = rq.front(); rq.pop();
            int dqFrontIdx = dq.front(); dq.pop();
            if(rqFrontIdx < dqFrontIdx) rq.push(rqFrontIdx + n); // 더 작은 index는 더 큰 index의 것을 없앤다. 그것이 optimal이다.
            else dq.push(dqFrontIdx + n);
        }

        if(!rq.empty()) return "Radiant";
        else return "Dire";
    }
};

/*
optimal 전략은 자기 다음에 있는 사람의 권리를 ban하는 것이다.
*/

 

시간복잡도

 시간복잡도 분석이 좀 어렵다. O(n)일까? 한 번의  while문에서 n/2개가 사라진다고 계산한다면 O(nlogn)이다.

 

공간복잡도

 n size queue를 2개 사용하기 때문에 O(n)이다.

 

후기

 독특하다.