[백준/Java] 15823 : 카드 팩 구매하기

백준 15823번 '카드 팩 구매하기' 풀이입니다. 이분 탐색으로 팩 길이 L을 결정하고, 슬라이딩 윈도우로 중복 없는 연속 구간을 M개 만들 수 있는지 확인합니다. 처음에는 가능한 N을 모두 시도하려 했지만 시간 초과가 예상돼 이분 탐색을 적용했고, 중복 없는 구간의 효율적 탐색에 슬라이딩 윈도우가 필요함을 깨달았습니다.

---

📌 문제 정보

• 번호: 15823
• 제목: 카드 팩 구매하기
• 난이도: Gold 2
• 분류: 이분 탐색, 슬라이딩 윈도우, 해시/배열(중복 체크)

---

💡 접근 방식

카드팩의 길이 L을 정하고, 길이 L인 연속 구간 중에서 중복 없는 구간을 겹치지 않게 M개 만들 수 있는지 검사했습니다.

---

🔹 단계별 풀이

1단계: L이 커질수록 조건을 만족하기 어려워지므로 이분 탐색으로 최대 L을 탐색

2단계: canBuy(L): 슬라이딩 윈도우로 중복 없는 구간 M개 가능한지 확인. last[x]로 마지막 등장 위치를 저장해 중복 발생 시 start를 점프. 윈도우 길이가 L이 되면 팩 확정 후 start = i+1

---

💻 핵심 코드

int answer = 0, max = N / M;
while (answer < max) {
    int mid = (answer + max + 1) / 2;
    if (canBuy(mid)) answer = mid;
    else max = mid - 1;
}

// canBuy 핵심
if (last[card] >= start) start = last[card] + 1;
last[card] = i;

if (i - start + 1 == buyCnt) {
    cnt++;
    if (cnt >= M) return true;
    start = i + 1;
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N log(N/M))
• 공간 복잡도: O(V)

---

📄 전체 코드

package B15823;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] cards;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        cards = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) cards[i] = Integer.parseInt(st.nextToken());

        int answer = 0, max = N / M;
        while (answer < max) {
            int mid = (answer + max + 1) / 2;
            if (canBuy(mid)) answer = mid;
            else max = mid - 1;
        }
        System.out.println(answer);
    }

    static boolean canBuy(int buyCnt) {
        if (buyCnt == 0) return true;
        int[] last = new int[500001];
        Arrays.fill(last, -1);
        int cnt = 0, start = 0;
        for (int i = 0; i < N; i++) {
            int card = cards[i];
            if (last[card] >= start) start = last[card] + 1;
            last[card] = i;
            if (i - start + 1 == buyCnt) {
                if (++cnt >= M) return true;
                start = i + 1;
            }
        }
        return false;
    }
}