가장 큰 수

· 문제 설명

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
[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

 

---

· Thinking 1

각 원소의 첫번째 인덱스 비교해서.. 오키오키 !
첫번째 인덱스를 어케 비교하지? 이걸 스트링으로 바꿔야되나,,?

 

만약 sort를 하면
3, 5, 9, 30, 34
이건 아닌데..
따로 담는다 치면 
9, 5, 3, 34, 30 이것도 아니고..

 

조합해서 만들 수 있는 모든 경우의 수를 담아서 가장 큰 값 ?.. ㅎㅎ

import java.util.ArrayList;
import java.util.Collections;

class Solution {
	public String solution(int[] numbers) {
		ArrayList<String> temp = new ArrayList<String>();
		perm(numbers, 0, numbers.length, numbers.length, temp);

		Collections.sort(temp);
		Collections.reverse(temp);
		
		if (temp.get(0).substring(0, 1).equals("0")) {
			return "0";
		} else {
			return temp.get(0);
		}
	}

	public static void perm(int[] arr, int depth, int n, int k, ArrayList<String> temp) {
		if (depth == k) {
			add(arr, k, temp);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, i, depth);
			perm(arr, depth + 1, n, k, temp);
			swap(arr, i, depth);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void add(int[] arr, int k, ArrayList<String> temp) {
		String str = "";
		for (int i = 0; i < k; i++) {
			if (i == k - 1) {
				str += arr[i];
				temp.add(str);
			} else {
				str += arr[i];
			}
		}
	}
}

ㅎㅎ 될리가 없지 테스트케이스 다 런타임 에러남..
너무 크게 돌아서 그런가봄..ㅎㅎ

그래 이건 아니였어 ㅎㅎㅎ;;

---

· Thinking 2

Comparator 써서 더한 값으로..

30과 3이면 330 과 303

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Solution {
	public static String solution(int[] numbers) {
		String answer = "";
		ArrayList<String> temp = new ArrayList<String>();
		for (int i = 0; i < numbers.length; i++) {
			temp.add(Integer.toString(numbers[i]));
		}

		Collections.sort(temp, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				if ((o1+o2).compareTo(o2+o1) > 0) {
					return -1;
				} else {
					return 1;
				}
			}
		});

		for (int i = 0; i < temp.size(); i++) {
			answer += temp.get(i);

			if (temp.get(0).equals("0")) {
				System.out.println("0");
				return "0";
			}
		}

		return answer;
	}
}

정확성 : 54.5 / 1-3, 5-6 런타임에러

---

· Thinking 3

다 쪼개서 비교해보깅

import java.util.ArrayList;

class Solution {
    public String solution(int[] numbers) {
      String answer = "";
      ArrayList<String> temp = new ArrayList<String>();

      while (temp.size() != numbers.length) {
      	int num = divideNum(numbers[0]);
      	int numIdx = 0;
      	for (int i = 1; i < numbers.length; i++) {
      		int num1 = divideNum(numbers[i]);

      		if (num < num1) {
      			numIdx = i;
      			num = num1;
      		} else if (num == num1) {
      			String str = "";
      			String str1 = "";
					
      			str += numbers[numIdx];
      			str += numbers[numIdx];
      			str += numbers[numIdx];
      			str1 += numbers[i];
      			str1 += numbers[i];
      			str1 += numbers[i];
					
      			if (str.compareTo(str1) < 0) {
      				numIdx = i;
      			}
      		}
      	}
			
      	temp.add(Integer.toString(numbers[numIdx]));
      	numbers[numIdx] = -1;
      }
		
      for (int i = 0; i < temp.size(); i++) {
      	answer += temp.get(i);
      	if (temp.get(0).equals("0"))
      		return "0";
      }
        
      return answer;
    }
    
    public static int divideNum(int n) {
    	if (n == 1000) {
    		n = 1;
    	} else if (n / 100 != 0) {
    		n /= 100;
    	} else if (n / 10 != 0) {
    		n /= 10;
    	}
        
    	return n;
    }
}

다르게 생각해봤는데 테스트 결과는 똑같음 ㅠ

정확성 : 54.5 / 1-3, 5-6 런타임에러

---

· Thinking 4

ArrayList에 굳이 안담고 그냥 배열에 담고 Arrays.sort 사용해보깅..

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	public static String solution(int[] numbers) {
		String answer = "";
		String[] nums = new String[numbers.length];
        
		for (int i = 0; i < numbers.length; i++) {
			nums[i] = Integer.toString(numbers[i]);
		}

		Arrays.sort(nums, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				if ((o1+o2).compareTo(o2+o1) > 0) {
					return -1;
				} else {
					return 1;
				}
			}
		});

		if (nums[0] == "0")
			return "0";

		for (String a : nums) 
			answer += a

		return answer;
	}
}

정확성 : 45.5 / 1-3, 5-6 런타임, 11 실패

---

· Thinking 5

어차피 정렬하는 거라 스트링 비교 후 반환값 자체를 반환값으로 넘겨서 시간 단축을 노려보자

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	public static String solution(int[] numbers) {
		String answer = "";
		String[] nums = new String[numbers.length];
        
		for (int i = 0; i < numbers.length; i++) {
			nums[i] = Integer.toString(numbers[i]);
		}

		Arrays.sort(nums, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return (o2+1-o1).compareTo(o1+o2);
			}
		});

		if (nums[0] == "0")
			return "0";

		for (String a : nums) 
			answer += a

		return answer;
	}
}

정확성 : 90.9 / 11 실패

아이고.. String의 같은 값 비교는 == 가 아닌 equals..^__^

---

· 완성 코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	public static String solution(int[] numbers) {
		String answer = "";
		String[] nums = new String[numbers.length];
        
		for (int i = 0; i < numbers.length; i++) {
			nums[i] = Integer.toString(numbers[i]);
		}

		Arrays.sort(nums, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return (o2+o1).compareTo(o1+o2);
			}
		});

		if (nums[0].equals("0"))
			return "0";

		for (String a : nums) 
			answer += a

		return answer;
	}
}

처음에도 이와 비슷하게 생각 했는데 시간 단축에서 애를 먹었당..

Comparator에 대해서 좀 더 공부를 해서 잘 다루어야겠담

 

* compareTo() 메서드 작성법
현재 객체 < 파라미터로 넘어온 객체: 음수 리턴
현재 객체 == 파라미터로 넘어온 객체: 0 리턴
현재 객체 > 파라미터로 넘어온 객체: 양수 리턴
음수 또는 0이면 객체의 자리가 그대로 유지되며, 양수인 경우에는 두 객체의 자리가 바뀐다.

---

· 참고

[Java] Comparable와 Comparator의 차이와 사용법 - Heee's Development Blog

---

· 문제 출처

알고리즘 연습 - 가장 큰 수 | 프로그래머스