[ 알고리즘 ] 코딩 - Programmers - 가장 큰 수.java

문제 링크

---

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

코딩테스트 연습 - 가장 큰 수

---

* Programmers - Level 2 - (자바) 가장 큰 수 - 정렬

입출력 예시

* 1000보다 작은 수라고 해서 자릿수를 비교해가며 하면 쉽게 풀리겠다!! 하고 접근했다가 완전 피 본 문제!!

* 자리수 비교를 하다 보면 이거 아닌데.. 하는 생각이 든다. 그때 빨리 턴 해야 한다!!

---

* 사용한 로직

* 자릿수 비교를 버리고 다시 생각해본 결과는 String의 CompareTo 

* 우선순위 큐(PriorytyQueue)의 빠른 힙 정렬을 이용해서 들어오는 숫자를 String으로 변환한 뒤 

* 문자열을 이었을 때 큰 수대로 내림차순 정렬

---

* 듣기로는 테스트케이스가 1000이하의 숫자라고 하지만 10000이하도 나온다고 한다.

* 더더욱 자릿수 비교를 하면 안된다!!

---

import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
    public String solution(int[] numbers) {
        // 우선순위 큐를 이용해서 내림차순 문자열 정렬
		PriorityQueue<String> pQueue = new PriorityQueue<String>(new Comparator<String>() {
			@Override // Comparator를 이용해서 내림차순 정렬
			public int compare(String o1, String o2) {
				return -(o1+o2).compareTo(o2+o1);
			}
		});
		
		int zerocnt = 0; // 0만 들어오는 경우 체크
		for(int i = 0; i < numbers.length; i++) {
			if(numbers[i] == 0) zerocnt++;
			pQueue.offer(String.valueOf(numbers[i])); // 문자열 변환
		}
        
		if(zerocnt == numbers.length) return "0";
		
		StringBuilder sb = new StringBuilder();
		while(!pQueue.isEmpty()) // 큐 안에 들어있는 숫자를 그대로 출력하면 정답
			sb.append(pQueue.poll());

        return sb.toString();
    }
}

---