[LeetCode-933] List.remove(0)이 느린 이유, 그리고 큐로 바꾸면 되는 이유

스택·큐 개념과 자주 쓰는 메서드는 카테고리 총정리 글에서 다룬다. 오늘 세팅한 5문제(1475/682/844/1047/933)의 마지막 문제다.

• 문제 링크: https://leetcode.com/problems/number-of-recent-calls/
• 파일 경로: src/main/java/coding_test/스택_큐/LC0933_NumberOfRecentCalls.java
• 난이도: Easy

문제 설명

ping(t)가 호출될 때마다 시각 t에 새 요청을 기록하고, [t - 3000, t] 범위(양 끝 포함) 안에 있었던 요청 개수를 반환하는 RecentCounter 클래스를 만든다. ping은 항상 이전 호출보다 큰 t로 호출된다.

ping(1)    -> 1
ping(100)  -> 2
ping(3001) -> 3
ping(3002) -> 3

시행착오

1. 문제 이해부터 헷갈림. ping(100)이 왜 1이 아니라 2인지부터 막혔다 — “이번 요청 하나만 세는 건가?”라고 생각했는데, 실제로는 “지금까지 쌓인 요청 중 범위 안에 있는 걸 전부 다시 센다”는 거였다. 100-1=99로 두 요청 사이 간격이 3000ms보다 훨씬 짧아서, 예전 요청(1)도 여전히 범위 안에 남아있는 것이었다.

2. ArrayList로 먼저 짰다가 성능 문제를 직접 겪음. List에 요청을 계속 추가하고, 범위 밖으로 나간 오래된 요청은 list.remove(0)로 지우는 식으로 짰는데, 이게 눈에 띄게 느렸다. ArrayList는 배열 기반이라 맨 앞 원소를 지우면 나머지 전부를 한 칸씩 당겨야 해서 O(n)이고, 이걸 반복하면 O(n²)가 된다는 걸 지적받고 나서야 원인을 이해했다.

3. Queue(ArrayDeque)로 바꿔서 해결. 큐는 앞/뒤 추가·제거가 전부 O(1)이라, “오래된 요청을 맨 앞에서부터 빼는” 이 문제에 훨씬 잘 맞았다. offer()로 새 요청을 뒤에 넣고, 맨 앞(peek())이 범위 밖으로 나갔으면 poll()로 계속 빼는 방식으로 재작성했다.

4. 필드를 static으로 선언했던 것도 고침. 901(StockSpanner)과 마찬가지로 “메서드가 반복 호출되며 상태를 기억해야 하는” 설계 문제였는데, 처음엔 Deque를 static 필드로 선언했었다. static은 이 클래스의 모든 객체가 공유하는 필드라는 뜻이라, 여러 개의 RecentCounter를 따로 만들면 상태가 섞여버린다. 인스턴스 필드로 바꿨다.

최종 코드

public class LC0933_NumberOfRecentCalls {

    Deque<Integer> queue = new ArrayDeque<>();

    public LC0933_NumberOfRecentCalls() {
    }

    public int ping(int t) {
        queue.offer(t);
        while (queue.peek() < t - 3000) {
            queue.poll();
        }
        return queue.size();
    }
}

오늘 배운 내용

“맨 앞(또는 맨 뒤)을 계속 빼야 하는” 문제에서는 자료구조 선택 자체가 성능을 결정한다. ArrayList도 논리적으로는 똑같은 결과를 낼 수 있지만, “맨 앞 삭제”라는 연산 하나가 O(n)이라는 것만으로 전체 알고리즘의 시간복잡도가 달라진다. 문제를 풀 때 “이 자료구조로 이 연산을 얼마나 빠르게 할 수 있는가”를 데이터 크기(10^4번 호출)와 함께 생각하는 습관이 필요하다는 걸 직접 성능 차이로 체감했다.

오답노트

• 틀렸던 패턴 1: 문제를 “이번 요청 하나만 판단”하는 걸로 오해.
• 왜 틀렸나: “최근 3000ms 안의 요청 개수”라는 표현을 “이번 요청이 최근인가”로 좁게 해석했다.
• 틀렸던 패턴 2: ArrayList + list.remove(0)로 오래된 요청 제거 — 느림.
• 왜 틀렸나: “맨 앞 원소 삭제”가 배열 기반 자료구조에서 O(n)이라는 걸 직접 겪기 전까진 몰랐다.
• 고친 패턴: Deque(큐)의 offer/poll로 교체 — O(1).
• 틀렸던 패턴 3: 상태를 저장하는 필드를 static으로 선언.
• 왜 틀렸나: 901에서 “인스턴스 필드”라는 개념을 배웠지만, 그게 static과 어떻게 다른지까지는 아직 명확하지 않았다.
• 다음에 떠올릴 시점: “맨 앞/맨 뒤를 자주 넣고 빼야 하는” 문제를 보면 ArrayList보다 Deque/Queue부터 먼저 고려한다. 그리고 클래스 필드를 선언할 때마다 “이게 객체마다 따로 있어야 하는 상태인가”를 확인해서 static 여부를 정한다.

감독관 메모

유저가 스스로 “아직 이 정도 실력은 아니다”라고 평가했다. 오늘(1475/682/844/1047/933) 다섯 문제를 통틀어 보면, 문제 이해 자체를 다시 확인해야 했던 경우(933)도 있었고, 성능 문제를 직접 겪고 나서야 자료구조를 바꾼 경우도 있었다 — 이건 “몬로토닉 스택 전용” 체크리스트를 넘어서 “스택/큐 전반에서 자료구조를 고르는 감각”이 아직 다지는 중이라는 뜻이다. 냉정하게 보면 여전히 진행형이지만, 오늘 안에서도 1475(실수 재발 안 함)처럼 좋아진 지점도 분명히 있었다.