골드3 - 백준 15823 카드 팩 구매하기

백준 15823 카드 팩 구매하기

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

접근방법

이 문제는 이분탐색으로 카드팩 내에 들어가는 카드 개수를 지정하여 만약 카드팩의 개수가 M보다 작으면 개수를 줄이고, M보다 크거나 같다면 카드 개수를 늘려주는 식으로 최대 카드 개수를 구하여주었다.

풀이

find함수를 정의해서 선택하는 카드 개수가 주어지면 투포인터를 이용해서 중복되지 않게 카드를 개수만큼 선택해서 총 카드팩의 수를 구해주어 반환하였다. 이 결과를 이용하여 이분탐색 함수 b_search에서 mid를 조절하여 upper bound를 찾아주어 반환해주었다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
bool visited[500001];
vector<int> cards;

int find(int num)
{
	int cnt = 0;
	queue<int> choice;
	int index = 0;
	while (index < cards.size())
	{
		if (visited[cards[index]])
		{
			visited[choice.front()] = false;
			choice.pop();
			continue;
		}

		visited[cards[index]] = true;
		choice.push(cards[index]);
		index++;
		if (choice.size() == num)
		{
			cnt++;
			while (!choice.empty())
			{
				visited[choice.front()] = false;
				choice.pop();
			}
		}
	}

	return cnt;
}

int b_search(int N, int M)
{
	int start = 1; 
	int end = N;

	while (start <= end)
	{
		int mid = (start + end) / 2;
		memset(visited, false, sizeof(visited));
		//cout << mid << endl;
		int t = find(mid);

		if (t < M)
			end = mid - 1;
		else
			start = mid + 1;
	}

	return end;
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		int card;
		cin >> card;
		cards.push_back(card);
	}

	cout << b_search(N, M) << endl;
	return 0;
}