[프로그래머스] 숫자 짝꿍 (Java)

 

문제

프로그래머스

 

알고리즘

우선순위 큐

 

풀이

X,Y의 최대 길이가 3,000,000 이기 때문에

2중 포문을 이용해 완전탐색으로 짝꿍을 찾으면 3,000,000² 의 연산으로 시간 초과가 발생한다.

 

따라서 X에서 각 수의 등장횟수를 세고, Y에도 각 수가 등장하면 우선순위 큐에 삽입한다.

이때도, 짝꿍이 최대 3,000,000개가 될 수 있으므로 O(n²)의 시간복잡도를 갖는 Array.sort()를 이용하면 시간초과가 나기 때문에

ArrayList에 담은 후 정렬을 진행하거나 우선순위 큐를 이용해 O(nlogn)의 시간복잡도로 해결한다. 

 

코드

import java.util.*;

class Solution {
	public String solution(String X, String Y) {
		int[] count = new int[10];
		PriorityQueue<Character> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < X.length(); i++)
			count[X.charAt(i) - '0']++;

		for (int i = 0; i < Y.length(); i++) {
			if (count[Y.charAt(i) - '0']-- > 0)
				pq.add(Y.charAt(i));
		}

		if (pq.isEmpty()) return "-1";
		if (pq.peek() == '0') return "0";

		StringBuilder sb = new StringBuilder();
		while (!pq.isEmpty())
			sb.append(pq.poll());
		return sb.toString();
	}
}