[Hackerrank 문제 풀이] Java Dequeue

Junu Kim·2025년 11월 17일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

40/46

[Dequeue] Java Dequeue

난이도: ★★★☆☆ • solved on: 2025-11-17

문제 요약

문제 유형: 슬라이딩 윈도우, 자료구조(Deque, HashMap)
요구사항:
크기 m의 연속된 부분 배열(subarray) 중에서 서로 다른 숫자의 개수(distinct count)가 최대가 되는 값을 구해야 한다.

사용 개념

자료구조
- Deque: 슬라이딩 윈도우 창 관리
- HashMap<Integer, Integer>: 각 숫자의 등장 빈도 저장
- HashSet: 최초 풀이에서 distinct 계산용으로 사용
알고리즘/기법
- 슬라이딩 윈도우(sliding window)
- 빈도 카운팅(frequency counting)
- 최대값 갱신(max tracking)
핵심 키워드
- 윈도우 크기 유지
- 중복 제거
- distinct 최대값 탐색

풀이 아이디어 및 코드

방법 1 : 최초 풀이 (Timeout 발생)

문제 분해

Deque에 숫자를 하나씩 넣으면서 크기를 m으로 유지

매번 new HashSet<>(deque).size()로 distinct를 구했음
핵심 로직 흐름
각 단계에서 deque 전체를 set으로 변환 → distinct 계산
한계

매번 O(m)으로 set 변환

시간제한 3초에서 TLE 발생

result 갱신 조건 실수로 인해 최대값 저장 실패 상황도 발생

코드

    import java.util.*;

    public class test {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Deque deque = new ArrayDeque<>();
            int n = in.nextInt();
            int m = in.nextInt();

            int result = 0;
            int tmp = 0;
            int size = 0;
            
            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                if(i<=m){
                    size = deque.size();
                }
                
                if(size<m-1){
                    deque.add(num);
                    continue;
                }
                
                if(size==m-1){
                    deque.add(num);  
                    result = new HashSet<>(deque).size();
                    continue;
                }
                
                if(size==m){
                    deque.add(num);
                    deque.pop();
                    tmp = new HashSet<>(deque).size();
                    result = result < tmp ? tmp : result;
                    if(result == m) break;
                }
                
            }
            System.out.println(result);
        }
    }

방법 2 : 개선된 풀이 (정답)

문제 분해

Deque로 슬라이딩 윈도우 창 유지

HashMap으로 빈도 관리

distinct는 증가/감소만 반영 → 매번 O(1)
핵심 로직 흐름
add num:
    freq[num]++
    if freq[num] == 1 → distinct++

if deque.size > m:
    old = deque.pop()
    freq[old]--
    if freq[old] == 0 → distinct--

result = max(result, distinct)
if result == m → 즉시 종료
장점

전체 시간복잡도 O(n)

HashSet 변환 없이 O(1)로 distinct 관리

timeout 해결

 import java.util.*;

    public class test {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Deque deque = new ArrayDeque<>();
            int n = in.nextInt();
            int m = in.nextInt();

            Map<Integer, Integer> freq = new HashMap<>();

            int result = 0;
            int distinct = 0;

            for (int i = 0; i < n; i++) {
                int num = in.nextInt();

                deque.add(num);
                freq.put(num, freq.getOrDefault(num, 0) + 1);
                if (freq.get(num) == 1) distinct++;

                if (deque.size() > m) {
                    int old = (int) deque.pop();
                    freq.put(old, freq.get(old) - 1);
                    if (freq.get(old) == 0) distinct--;
                }
                
                if (deque.size() == m) {
                    result = Math.max(result, distinct);
                    if (result == m) break;
                }
            }

            System.out.println(result);
        }
    }

시간·공간 복잡도

방법 1 (TLE)

시간 복잡도: O(n × m)
공간 복잡도: O(m)

방법 2 (최적)

시간 복잡도: O(n)
공간 복잡도: O(m)

어려웠던 점

문제에서 요구하는 것이 “m 사이즈 연속 부분 배열 중 distinct 최대”임을 이해하는 데 시간이 필요했다. (문제 접근 자체가 조금 난감했음)
result를 갱신할 때 현재 distinct <= result 체크 없이 매번 덮어써서 최대값이 저장되지 않는 문제 발생.
슬라이딩 윈도우 크기를 m이 아닌 예시 값 3으로 고정해버린 실수를 했었다.
HashSet 변환이 각 반복마다 발생해 O(m)의 비용이 누적되어 timeout이 반복되었다.
result의 최대 가능값이 m이라는 점을 이용해 조기 종료해도 여전히 timeout → 핵심 병목은 “매번 Set 생성”이라는 점을 뒤늦게 파악했다.
Java Stream 기반의 Set 변환(Collectors.toSet()) 역시 내부적으로 매우 느려 문제 해결에 부적합했다.