[ 알고리즘 ] 코딩 - Programmers - 숫자게임.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/12987

코딩테스트 연습 - 숫자 게임

---

문제 개요

프로그래머스 - Level 3 - (자바) 숫자게임 - 우선순위 큐를 이용한 Heap 정렬

문제 설명

 

제한 사항

입출력 예시

B가 A보다 큰 숫자의 갯수 중 최대가 되는 경우 얼마인가? 하는 문제

---

 

로직

Step 01. A배열과 B배열을 Heap 정렬하면서 저장할 우선순위큐를 2개 준비한다.

Step 02. A배열과 B배열을 오름차순 PQ에 저장한다.

Step 03. A_PQ(a)와 B_PQ(b)의 값을 비교한다.

Step 04. b 가 a 보다 큰 경우만 A_PQ와 B_PQ 둘 다 poll()한다. answer++

Step 05. b 가 a 이하라면 B_PQ만 poll()해서 A보다 큰 B 값을 찾는다.

Step 06. Step 03 부터 Step 05까지를 A_PQ나 B_PQ 둘 중 하나라도 빌 때까지 반복한다.

Step 07. 누적된 answer가 정답!

 

level3 치고는 간단한 문제였다. 시간초과가 걱정이 돼서 PQ로 구현했는데, 다른 사람의 코드를 보니 그냥 Arrays.sort를 이용해도 시간초과가 나지않는 것 같다.

---

코드

import java.util.PriorityQueue;
class Solution {
	public int solution(int[] A, int[] B) {
		PriorityQueue<Integer> A_pQueue = new PriorityQueue<Integer>();
		PriorityQueue<Integer> B_pQueue = new PriorityQueue<Integer>();

		int length = A.length;
		for (int i = 0; i < length; i++) {
			// 전체 오름차순 Heap 정렬
			A_pQueue.offer(A[i]);
			B_pQueue.offer(B[i]);
		}

		int answer = 0;
		// A 혹은 B의 큐가 다 빌 때까지
		while (!A_pQueue.isEmpty() && !B_pQueue.isEmpty()) {
			// A와 B의 숫자 판단
			int a = A_pQueue.peek();
			int b = B_pQueue.peek();

			if (b > a) { // B가 A보다 큰 경우만 둘 다 뺀다
				A_pQueue.poll();
				B_pQueue.poll();
				answer++;
			} else if (b <= a) {
				// B가 같거나 작은경우 승점을 얻지못함. B만 뺀다
				// B만 빼야 A보다 큰 수가 있는지 판단 가능
				B_pQueue.poll();
			}
		}

		return answer;
	}
}