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

문제

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

15823번: 카드 팩 구매하기

N개의 카드가 일렬로 진열되어 있다.

주띵이는 진열된 카드중에 몇개의 연속된 카드를 뽑아 하나의 카드팩을 만드는 방식으로  M개의 카드팩을 만들려고한다.

이때 카드팩은 모두 동일한 수의 카드가 들어가 있어야 하고 카드는 중복해서 뽑을 수 없으며 하나의 카드팩에 동일한 숫자의 카드가 들어갈 수 없다.

카드팩안에 들어갈 수 있는 카드의 최대 갯수를 구하는 문제다.

---

풀이

결정문제 + 투포인터로 풀리는 문제다.

N개의 카드중에 연속된 K개의 카드를 뽑아 하나의 카드팩을 만든다고 가정하자. 이때, K의 갯수는 최대 N / M개(최악의 경우 100,000개)가 나올수 있다.

따라서, 최악의 경우 log(2)[100,000] = 16 만큼 반복하므로, 이분탐색을 이용해 K의 범위를 좁혀가며 최대 카드 갯수를 빠르게 구할 수 있는데, 간단하게 다음 질문을 만족하는 K값을 찾아준다고 가정하면 된다.

 

하나의 카드팩에 K개의 카드를 넣어 M개의 카드팩을 만들 수 있는가?

yes -> 더 많은 카드로 M개의 카드팩을 만들 수 있는지 확인해야 하므로, left = K + 1;

no -> 더 적은 카드로 M개의 카드팩을 만들 수 있는지 확인해야 하므로, right = K - 1;

 

다음으로, K를 선택했을때, 카드를 뽑는 과정에서 투 포인터를 사용했다. "연속된 카드"를 뽑는 조건때문에, 투 포인터로 O(N)만에 모든 카드를 뽑아줄 수 있는데,

left = 카드를 뽑기 시작한 위치

right = 마지막 카드 위치

로 가정하고, 탐색을 하면된다.

right를 늘려가다가, 카드가 중복된다면, (내 풀이에서는 왼쪽부터 탐색했으므로 겹치는경우는 없다.) left를 증가시키며, left에 선택된 카드를 선택 해제하면 된다.

 

주요 소스코드

1. 결정알고리즘

	private int getCardsInPack(){
		int left = 1, right = this.cards.length / this.packs, answer = 1;
		for(int i = 0; i < 17 && (left <= right); i++){
			int mid = (left + right) / 2;
			if(this.packable(mid)) {
				left = mid + 1;
				answer = max(answer, mid);
			}
			else right = mid - 1;
		}
		return answer;
	}

 

2. 투 포인터

	private boolean packable(int cardsInPack){
		int madePack = 0, trig = 0;
		int[] picked = new int[500001];
		for(int start = 0; start < this.cards.length; start++){
			int left = start, right = start;
			trig++;
			picked[this.cards[left]] = trig;
			while(true){
				if(right - left + 1 == cardsInPack){
					madePack++;
					break;
				}
				if(left > right || right+1 == this.cards.length) break;
				if(picked[this.cards[right+1]] == trig){
					picked[this.cards[left]] = 0;
					left++;
					continue;
				}
				picked[this.cards[right+1]] = trig;
				right++;
			}
			start = right;
		}
		return madePack >= this.packs;
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/15823%20%EC%B9%B4%EB%93%9C%20%ED%8C%A9%20%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃