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

https://www.acmicpc.net/problem/15823

15823번: 카드 팩 구매하기

 

이분탐색을 이용해서 특정 수량의 카드팩을 구성할 수 있는지 확인하는 방법으로 카드팩을 구성할 수 있는 최대 수량을 구했다. 이때, 특정 수량의 카드팩을 구성할 수 있는지 확인하는 방법은, 투 포인터를 이용해 카드 목록을 확인해 보며 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;

int n, m;
vector<int> cards;

//num 수량의 카드팩을 구성할 수 있는지 확인
bool check(int num) {

	int cnt = 0;
	unordered_set<int> check_card;

	//투포인터를 이용해 확인
	int left = 0;
	int right = 0;
	while (1) {

		if (cnt >= m) {
			break;
		}

		//하나의 카드팩을 만들었을때
		if (check_card.size() == num) {
			cnt++;

			check_card.clear();
			left = right;
			continue;
		}

		if (right >= n) {
			break;
		}

		//right에 있는게 현재 팩에 포함될 수 있을떄
		if (check_card.count(cards[right]) == 0) {
			check_card.insert(cards[right]);
			right++;
		}

		//right에 있는게 현재 팩에 포함될 수 없을때
		//left를 왼쪽으로 옮긴다
		else {
			check_card.erase(cards[left]);
			left++;
			continue;
		}

	}

	if (cnt >= m) {
		return true;
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		cards.push_back(input);
	}

	int left = 1;
	int right = n;
	int result = 0;
	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid)) {
			result = mid;
			left = mid + 1;
		}

		else {
			right = mid - 1;
		}
	}

	cout << result;

	return 0;
}