[LeetCode 75/Queue] 993 - Number of Recent Calls / 649 - Dota2 Senate (Java)

993 - Number of Recent Calls

---

풀이

• `RecentCounter()`: 최근 요청 수 0으로 초기화
• `int ping(int t)`: 시간 t에 새로운 요청 추가, 지난 3000밀리초 동안 발생한 요청 수(새로운 요청 포함) 반환
  / [t - 3000, t ] 범위 내에서 발생한 요청 수 반환

=> 시간 t 계속 증가 -> 최근 3000ms 안에 있는 요청만 유지

=> Sliding Window + Queue (새로운 요청 뒤에 추가, 오래된 요청 앞에서 제거: FIFO)

Queue<Integer> q;

 

생성자

public RecentCounter() {
    q = new LinkedList<>();
}

 

`ping(int t)`: t 기준으로 지난 3000ms 안에 있는 요청 수 반환

• q.offer(t)
• [t - 3000, t] -> `q.peek() < t - 3000` => 범위 밖 -> 제거 => 오래된 요청 제거: `q.poll()`

public int ping(int t) {
    q.offer(t);

    while (!q.isEmpty() && q.peek() < t - 3000) {
        q.poll();
    }

    return q.size();
}

• ex. ping(1)
  • 범위: [-2999, 1]
  • 요청: [1] => 1개
• ex. ping(100)
  • 범위: [-2900, 100]
  • 요청: [1, 100] => 2개
• ex. ping(3001)
  • 범위: [1, 3001]
  • 요청: [1, 100, 3001] => 3개
• ex. ping(3002)
  • 범위: [2, 3002]
  • 요청: [1, 100, 3001, 3002] => 3개

---

코드

class RecentCounter {
    Queue<Integer> q;

    public RecentCounter() {
        q = new LinkedList<>();
    }
    
    public int ping(int t) {
        q.offer(t);

        while (!q.isEmpty() && q.peek() < t - 3000) {
            q.poll();
        }

        return q.size();
    }
}

---

649 - Dota2 Senate

---

풀이

Doat2 세계에 Radiant/Dire 두 진영 존재, 두 가지 권한 중 하나 행사

• R - 상원의원 한 명 권리 박탈: 이번 및 이후
• D - 승리 선언: 투표권 가진 상원의원 모두 같은 당 소속 -> 승리 선언 

=> 각 사람은 자기 턴이 오면 상대 한 명 제거

-> 누가 더 빨리 등장하는지 중요 => 위치(index) 저장

Queue<Integer> radiant = new LinkedList<>();
Queue<Integer> dire = new LinkedList<>();

for (int i = 0; i < n; i++) {
    if (senate.charAt(i) == 'R') radiant.offer(i);
    else dire.offer(i);
}

 

현재 가장 앞에 있는 R과 D 대결

• rIdx < dIdx: R이 먼저 등장 = R이 먼저 행동 -> D 제거, R 남음
  • `radiant.offer(rIdx + n)`: 다음 라운드의 맨 뒤에서 다시 등장 -> 라운드 순환 구조

while (!radiant.isEmpty() && !dire.isEmpty()) {
    int rIdx = radiant.poll();
    int dIdx = dire.poll();

    if (rIdx < dIdx) radiant.offer(rIdx + n);
    else dire.offer(dIdx + n);
}

---

코드

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();

        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') radiant.offer(i);
            else dire.offer(i);
        }

        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int rIdx = radiant.poll();
            int dIdx = dire.poll();

            if (rIdx < dIdx) radiant.offer(rIdx + n);
            else dire.offer(dIdx + n);
        }

        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode