[백준 / 골드2] 15823 카드 팩 구매하기 (Java)

문제 보기

사용한 것

• 효율적으로 최대 카드 수를 구하기 위한 upper bound
• 효율적으로 원하는 카드팩 수를 만들 수 있는지 확인하기 위한 투포인터

풀이 방법

• 최대 카드 수를 효율적으로 구하기 위해서 upper bound를 사용한다.
• 선택한 카드 수로 원하는 카드팩 수를 만족할 수 있는지 확인하기 위해 투포인터를 사용한다.
  • 선택하지 않은 카드면 ct, r 증가, picked에 카드 추가
  • 선택한 카드면 이전에 선택한 카드 다음 인덱스로 l, r 설정하고 ct, picked 초기화
  • ct가 선택한 카드 수(numOfCards)가 되면 카드팩 수(numOfCardPacks) 증가
  • numOfCardPacks가 원하는 카드팩 수(m)이 되면 return true

코드

public class Main {

    private static int n;
    private static int m;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(findMaxNumOfCards());
    }

    private static int findMaxNumOfCards() {
        // upper bound
        int l = 1;
        int r = n / m;
        while (l <= r) {
            int mid = (l + r) / 2;

            if (isPossible(mid)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return r;
    }

    private static boolean isPossible(int numOfCards) {
        // 투포인터
        int l = 0;
        int r = 0;
        int ct = 0;
        Set<Integer> picked = new HashSet<>();
        int numOfCardPacks = 0;
        while (r < n) {
            int card = arr[r];

            if (!picked.contains(card)) {
                ct++;
                r++;
                picked.add(card);
            } else {
                while (arr[l] != card) {
                    l++;
                }
                l++;
                r = l;
                ct = 0;
                picked.clear();
            }

            if (ct == numOfCards) {
                numOfCardPacks++;
                l = r;
                r = l;
                ct = 0;
                picked.clear();
            }

            if (numOfCardPacks == m) {
                return true;
            }
        }

        return false;
    }
}