프로그래머스 - 가장 큰 수

# 문제

https://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 합니다.

 

# 풀이 (자바) 

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

public class Solution {	 
	 public static String solution(int[] numbers) {
	        String answer = "";
	        ArrayList<String> list = new ArrayList<>();
	        
	        for(int i=0; i < numbers.length; i++) { 
	          list.add(Integer.toString(numbers[i])); 
	        } // int 배열을 String 배열로 변환해 list 에 저장 

	      Collections.sort(list, (a, b) -> (b + a).compareTo(a+b));
	      // sort 를 하되, compareTo 라는 식을 이용해서
	      // 단순히 a , b 를 비교하는 게 아니라  (ex. 30 VS 3) = 30, 3
	      // (a + b) 과 (b + a) 을 비교  	(30+3= 303 VS 3+30 = 330) = 3, 30 
	      for (int j = 0; j <list.size(); j++) { // sort 된 리스트를 answer 에 입력하는 for 문 
	    	  if (answer.equals("0") && list.get(j).equals("0")) {   // 0 이면 
		    		  list.remove(j); // 리스트에서 지워줌 
		    		  continue;
				  }
	    		 answer += list.get(j); // 그 외는 answer 에 더하고 
			     list.remove(j); // 리스트에서 지움
			     j--; 
	    		}  
	        return answer;
	    }
 }

 

# 한 줄 느낌

ArrayList 에 담아 sort 를 주는 것 까지는 쉬웠는데, a + b 와 b + a 를 비교한다는 알고리즘을 생각해내기가 어려웠다. 시간이 넉넉히 주워진다고 해도 혼자 떠올리기는 쉽지 않을 것 같긴하다. 처음에는 제일 큰 자릿수의 값이 같으면 -> 두번째로 큰 자릿수의 값 비교 및 전체 자릿수 비교를 하려고 했는데 두 비교를 동시에 하는 알고리즘을 짜는 것이 쉽지 않았다. 코드도 길어지고 해야할 예외처리도 많았는데, compareTo 를 사용해 a + b , b + a 를 비교하기만 하면 너무 쉽고 깔끔하게 되더라... 다음 시간에는 compareTo 를 정리해오도록 하겠다!