[23757]아이들과 선물 상자

문제

알고리즘

문제요약

각 아이들이 가져가기를 원하는 선물의 개수가있는데, 각각 다른 개수가 담겨있는 선물상자 중 한 상자로 한 아이가 원하는만큼 선물을 나누어주면서, 어떤 상자든 한 아이당 한 상자로 모든 아이들을 커버할 수 있는지 묻는 문제이다. 이전에 다른 아이가 선택한 상자를 또 사용해도 괜찮다.

사용 가능한 자료구조

• 우선순위 큐
  아이가 원하는 선물의 개수 중 가장 큰것과 가장 많은 선물을 담고있는 선물상자를 비교하며 진행해야 모든 아이들이 원하는만큼 선물을 가져갈 수 있는지 알아볼 수 있으므로, 최대값을 가장 높은 우선순위로하는 우선순위 큐를 사용할 수 있다.
• 배열
  배열은 값을 넣는대로 index를 가져가므로, 모든 값을 입력받은 후 내림차순으로 정렬하면 가장 큰 값이 어떤값인지 알 수 있으므로 배열을 사용할 수 있다.

생각한 알고리즘

• 우선순위 큐
  각 상자마다 들어있는 선물개수(amountOfN)와 각 아이들이 원하는 선물의개수(wantGift)를 모두 높은숫자를 우선순위로 하는 우선순위 큐를 사용한다. 가장 높은 우선순위의 값끼리 비교하여, 'amountOfN < wantGift'이면 '0'을 출력하고 끝낸다. 만약 그렇지않다면 'amountOfN = amountOfN - wantGift'을 하고, wantGift의 가장높은 우선순위의 값을 제거한다. 그리고 앞에서 했던 작업을 반복한다. 이렇게 반복하며 wantGift에 있는 원소개수가 0이라면 모든 아이들이 선물을 가져갈 수 있는 상황이므로 '1'을 출력하고 프로그램을 끝낸다.

• 배열
  각 상자마다 들어있는 선물개수(amountOfN)와 각 아이들이 원하는 선물의개수(wantGift)의 배열을 내림차순으로 정렬한다. 정렬 후 두 배열의 첫번째 원소끼리 비교하되, 'amountOfN < wantGift'이면 '0'을 출력하고 끝낸다. 만약 그렇지않다면 'amountOfN = amountOfN - wantGift'을 하고, wantGift의 첫번째 원소를 제거한다. 그리고 앞에서 했던 작업을 반복한다. 반복하며 wantGift배열의 원소개수가 0이되면 '1'을 출력하고 프로그램을 끝낸다.

• '우선순위큐 + 배열'로 최종수정하였다.
  amountOfN의 로직은 우선순위큐를 사용하여 그대로 유지하고, wantGift은 1~M까지 순서대로
  배열에 넣어준 후, 각 첫 원소끼리 비교하면서 위에서 짠 알고리즘을 반복한다. 대신 wantGift가 배열이기때문에 첫번째 원소를 제거하는과정대신 0으로 수정하는 작업을 한다. 이후 wantGift의 원소중 0이아닌 원소의 개수가 0개이면 1을 출력하고 프로그램을 끝낸다.

시간복잡도

예상

• 우선순위 큐
  값을 받아 넣는 작업을 O(logN) N번 각각 하므로 (2NlogN). amountOfN과 wantGift에서 우선순위가 가장 높은값을 조회 O(1)하는데, 각각 N번 하므로 O(2N). amountOfN의 값 수정 O(1)을 N번 하므로 O(N). wantGift의 우선순위가 가장 높은값을 제거 O(logN) 하는데 N번 진행하므로 O(NlogN).
  -> 총 3N + 3NlogN = O(NlogN)
  N의 최대값은 10^5이므로 최악의 케이스인경우 5*10^5가 되는데, 이는 1억보다 작으므로 1초안에 가능할것으로 판단된다.

• 배열
  두 배열에 값을 넣는 작업 O(1)을 각각 N번 반복하므로 O(2N). 선택정렬O(N^2)을 이용해 내림차순으로 두 배열 모두 정렬해야하므로 O(2N^2). 첫 원소를 N번 접근하며, 이는 두 배열에서 이루어지므로 O(2N). 선물상자배열은 원소를 N번 수정O(1)하므로 O(N). 아이들의 배열은 N번 배열원소가 삭제O(N)되므로 O(N^2).
  -> 총 3N^2 +5N = O(N^2)
  N의 최대값은 10^5이므로 최악의 케이스인경우 10^10인데, 이는 1억보다 큰수이기때문에 1초를 넘겨서 시간초과가 날 것으로 판단된다.

• 우선순위큐 + 배열을 사용하는 로직으로 수정하였다.
  -우선순위큐 : 값을 받아 넣는 작업을 O(logN) N번 하므로 (NlogN). amountOfN의 우선순위가 가장 높은값을 조회 O(1)하고 N번 반복하므로 O(N). amountOfN의 값 수정 O(1)을 N번 하므로 O(N).
  -배열 : 배열에 값을 넣는 작업 O(1)을 N번 반복하므로 O(N). 첫 원소를 N번 접근하므로 O(N). 첫 원소를 0으로 N번 수정O(1)하므로 O(N).
  -> 총 5N + NlogN = O(NlogN)
  N의 최대값은 10^5이므로 최악의 케이스인경우 5*10^5가 된다. 따라서 1초안에 가능할것으로 판단된다.

결과

808ms

작성한 코드

import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Collections;

public class Main {

	public static void main(String[] args) {
		PriorityQueue<Integer> amountOfNPriorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());
		Scanner kb = new Scanner(System.in);
		
		String inputs = kb.nextLine();
		String[] strArr = inputs.split(" ");
		
		int N  = Integer.parseInt(strArr[0]);
		int M  = Integer.parseInt(strArr[1]);
		
		String gifts = kb.nextLine();
		String[] giftsArr = gifts.split(" ");
		Integer[] amountOfN = new Integer[N];
		
		String want = kb.nextLine();
		String[] wantArr = want.split(" ");
		Integer[] wantGift = new Integer[M]; 
		
		for(int i =0; i<N ; i++) {
			amountOfN[i] = Integer.parseInt(giftsArr[i]);
			amountOfNPriorityQueueHighest.offer(amountOfN[i]);
		}
		
		for(int i =0; i<M ; i++) {
			wantGift[i] = Integer.parseInt(wantArr[i]);
		}
		
		for(int i =0; i < M ; i++) {
			if(amountOfNPriorityQueueHighest.size() == 0) {
				System.out.println("0");
				break;
			}else {
				int interval = amountOfNPriorityQueueHighest.peek() -wantGift[i];
				if(interval < 0) {
					System.out.println("0");
					break;
				}
				else {				
					amountOfNPriorityQueueHighest.poll();
					if(interval !=0) amountOfNPriorityQueueHighest.offer(interval);
					wantGift[i] = 0;
				}
			}
		}
		int count =0;
		for(int i =0; i<M; i++) {
			if(wantGift[i] != 0) count++;
		
		}
		if(count ==0) System.out.println("1");
		return;
	}
}

헤맸던 부분과 해결방법 및 느낀점

• 시간복잡도를 구할 때, '3N + 2NlogN'이 나오면 두 항중 어떤 값이 더 큰 영향을 주는지 어떻게 판단하지?
  -> 해결방법 : 일단 3N과 2NlogN에서 판단하는게아니라, 이 두개에서도 계수를먼저 없애서 N과 NlogN으로 만든 후 판별한다. 그럼 결국 N<NlogN 이므로 O(NlogN)이다.

• 두번째 예제입력은 제대로 출력되는데, 첫번째 예제를 입력하면 아래와같은 에러가 났다.
  
  디버깅으로 값이 잘 들어가있는것을 확인했는데, 왜 null이라는 에러가 떴을까?
  -> 원인 : if()조건문으로 들어간 poll()연산 if(wantGiftPriorityQueueHighes.poll() == null)때문에, for문을 한 번 돌때마다 원소가 2개씩 없어지는게 문제였다.
  -> 해결방법 : poll()을 peek()으로 수정해주었다.
  -> 느낀점: if()조건문에 들어가는것도 연산이 적용되는거였나? 나는 이 기본적인것을 모르고있었던것이다. 조건문의 '결과'가 true인지 false인지에 따라 실행문의 실행여부가 달라지는거고, 조건문의 연산은 무조건 실행되는것이다!!
  이를 테스트하기위해 실수했던 우선순위큐를 사용한 코드를 짜보았다.

import java.util.PriorityQueue;
import java.util.Collections;

public class Test {
	public static void main(String[] args) {
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for(int i =1; i<6; i++) {
			queue.offer(i);
		}
			System.out.println("맨 앞 원소 : " + queue.peek());
			queue.poll();
			System.out.println("1번 poll후, 맨 앞 원소 : " + queue.peek());
			if(queue.poll() == null) System.out.println("if문");
			System.out.println("if문 실행후, 맨 앞 원소 : " + queue.peek());
	}
}

아래 이미지는 위 코드의 결과이다.

if문을 실행한 후에도 맨 앞의 원소가 삭제된것을 알 수 있다.

• 첫번째 예제를 넣었을 때, for문을 한 번 돌고 나오기전에 wantGiftPriorityQueueHighes 원소 값은 1 2 1이 되어야하는데, 2 1 2이 되어있는 이상한 문제가 있다. 첫번째 for문을 완전히 끝내면 다시 1 2 1로 바뀐다. 아래 사진은 for문 속 작업은 끝냈지만 빠져나오기전이다.
  
  또한 amountOfNPriorityQueueHighest에는 원래 들어간 순서가 4 3 2 1 이고, 앞의 4를 없앤후 1을 뒤에 추가한거니까 3 2 1 1의 순서가 되어야하는데, 왜 3 1 2 1 이 되는건지 모르겠다.
  
  -> 원인 및 분석 : 계속 돌려보고 찾아 본 결과, 이 두 문제의 원인은 우선순위큐는 자동으로 수를 비교하여 정렬되는구조이기때문에 이것이 메모리상에서 적용되고 돌아가는 시점의 파악문제였던것으로 결론났다. 결국 문제가 아니었고, 정상적인것이었던것이다.

위 까지의 헤맸던 부분과 해결방법 및 느낀점은 아이들 자료구조를 우선순위큐로 사용하고있을 때 했던 고민들이다.

• 예제의 결과는 잘 맞는데, 제출하면 '틀렸습니다'를 받았다.
  -> 원인 : 독해력의 문제였다. 아이들은 1~M까지 순서대로 현재 가장 선물이 많은 상자에서 선물을 가져가야하는데, 아이들의 순서도 상관없는줄알고, 선물상자와 아이들을 모두 우선순위 큐를 사용했다.
  -> 해결방법 : 선물상자는 그대로 높은값을 우선순위로하는 우선순위큐를 사용했고, 아이들은 배열을 사용해서 해결했다.
  -> 느낀점 : 마냥 어떤 로직을 사용할지 어떤 자료구조를 사용할지 고민할게아니라, 먼저 문제를 천천히 읽으면서 문제의 요구사항을 놓치지않게 잘 체크하는 습관을 가져야겠다.

찾아본 지식

• 배열에 원소를 추가할 때에는 add()를 사용하면 안되고, 배열명[index] = 값으로 해야한다.

• 배열연산의 시간복잡도

• 배열 원소 삭제방법