(C++, Rust) - LeetCode (easy) 933. Number of Recent Calls

https://leetcode.com/problems/number-of-recent-calls/description/

Number of Recent Calls - LeetCode

자료구조를 이용하거나 이분탐색을 사용해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

requests정보를 저장할 자료구조를 class또는 구조체 내부에 member로 선언해 주며 instance생성 시점에 공간을 할당해줍니다.* rust의 경우 ping이 &self를 받으나 request에 정보를 추가하기 위해서 내부 가변성을 사용해줘야합니다. borrow_mut사용을 위해 RefCell로 선언해줍니다.

📔 풀이과정

공통 : queue나 deque을 이용해 ping호출시마다 t를 requests에 넣어줍니다.

1. 자료구조를 이용한 풀이t - 3000보다 작은 원소들을 왼쪽부터 pop front해주고 남은 requests의 길이를 반환합니다.

 

2. 이분탐색을 이용한 풀이t - 3000의 lower_bound를 찾아 현재 requests.size() - lower_bound index값을 반환합니다.

---

📕 Code

📔 C++

📑 queue 이용

class RecentCounter {
public:
    queue <int> requests;
    
    int ping(int t) {
        requests.push(t);
        while(requests.size() && requests.front() < t - 3000) {
            requests.pop();
        }
        return requests.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

📑 이분탐색 

class RecentCounter {
public:
    vector <int> requests;
    
    int ping(int t) {
        requests.push_back(t);
        auto idx = lower_bound(requests.begin(), requests.end(), t-3000) - requests.begin();
        return requests.size() - idx;
    }
};
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

📔 Rust

use::std::collections::VecDeque;
use std::cell::RefCell;

struct RecentCounter {
     requests: RefCell<VecDeque<i32>>,
}


/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl RecentCounter {

    fn new() -> Self {
        RecentCounter {
            requests: RefCell::new(VecDeque::new())
        }
    }
    
    fn ping(&self, t: i32) -> i32 {
        let mut requests = self.requests.borrow_mut();
        requests.push_back(t);

        while let Some(&front) = requests.front() {
            if front < t - 3000 {
                requests.pop_front();
            } else {
                break;
            }
        }
        requests.len() as i32
    }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * let obj = RecentCounter::new();
 * let ret_1: i32 = obj.ping(t);
 */

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.