[프로그래머스] 가장 큰 수(42746)_Array

문제

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

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

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

	numbers	return
예제1	[6, 10, 2]	6210
예제2	[3, 30, 34, 5, 9]	9534330

 

코딩 풀이

import java.util.PriorityQueue;

class P implements Comparable<P>{
	int num;
	int index;
	
	public P(int num, int index) {
		this.num=num;
		this.index=index;
	}
	
	@Override
	public int compareTo(P o) {
		return o.num-this.num;
	}
}

public class Solution_42746_1 {
	
	public static void main(String[] args) {
//		int[] numbers = {0,0,0,0,0};
//		int[] numbers = {6, 10, 2};
		int[] numbers = {3, 30, 34, 5, 9};
		System.out.println(solution(numbers));
	}
	public static String solution(int[] numbers) {
        String answer = "";
        String numberStrArr[] = new String[numbers.length];
        for(int i=0;i<numbers.length;i++) {
        	numberStrArr[i] = transferNum(numbers[i]+"");
        }
        
        PriorityQueue<P> pq = new PriorityQueue<>();
        for(int i=0;i<numbers.length;i++) {
        	pq.add(new P(Integer.parseInt(numberStrArr[i]), i));
        }
        int ansNum = 0;
        while(!pq.isEmpty()) {
        	P p = pq.poll();
        	ansNum+=numbers[p.index];
        	answer+=numbers[p.index];
        }
        
        if(ansNum==0) {
        	answer = "0";
        }
        
        return answer;
    }
	public static String transferNum(String numStr) {
		String transStr = "";
		while(transStr.length()<5) {
			transStr+=numStr;
		}
		transStr=transStr.substring(0, 4);
		return transStr;
	}
}

 

코딩 풀이

1. 조합을 이용하여 완전 탐색

• numbers 에 있는 모든 변수들을 조합하여 만드는 수 중에서 가장 큰 값을 만드는 것
• 경우의 조합은 O(len(numbers)!) 인데, O(100000!) 는 무한대로 나온다.

 

 

2. numbers 내 모든 숫자를 4자리 숫자로 만들어 비교한다.

• numbers 에 원소는 0이상 1000이하이므로 1000x100000 = 10^8 (1억) 수행 시간은 약 0.011초이다.

 

• 그러므로 원소들을 모두 4자리 숫자로 만들어서 비교작업을 진행한다.
• 4자리 숫자를 비교해 원소들을 문자열로 합치는 작업을 진행한다.
• *** 마지막으로 numbers 배열이 {0,0,0,0,0} 일 경우 00000 이 아니고 0 이므로 더한 값이 0일 경우에는 0으로 출력한다.

 

참고
https://dailyheumsi.tistory.com/102