프로그래머스: 가장 큰 수

문제 설명

• 숫자의 순서를 적절히 변경해 가장 큰 수를 만드는 문제입니다.

접근법

3줄 요약

• 숫자의 첫번째 값이 다르면 일반적인 정수 대소비교를 진행하면 됩니다.
• 숫자의 첫번째 값이 다르면 다음 두 경우의 수에 따라 대소비교 방법이 달라집니다.
  • 두 숫자의 자릿수가 같으면 정수 대소비교를 진행하면 됩니다.
  • 두 숫자의 자릿수가 다르면 자릿수가 짧은 숫자를 복제시켜 자릿수를 맞춘 후 대소비교를 해야 합니다.
    • 복제는 해당 숫자를 계속 반복하는 형태로 진행하는데 그 이유는 짧은 숫자의 머리(a)와 긴 숫자에서 짧은 숫자를 제외한 첫번째 숫자(c)의 대소에 의해 전체 대소가 결정되기 때문입니다.
• 

전문

• 문제에서는 완전탐색을 보여줬지만 실제로는 완전탐색을 하면 최대 1000!의 경우의 수가 발생하기 때문에 완전탐색이 불가능합니다.

• [3,30,34,5,9]의 예시를 통해 우리는 숫자로 정렬하는것도, 숫자를 문자열로 변경해 정렬하는 것도 정답이 아니라는 걸 알 수 있습니다.

  • 가장 큰 수를 얻기 위해서는 현재의 값으로 비교하는 것이 아니라 일정한 조건으로 변경된 값으로 대소를 비교해야 함을 알 수 있습니다.
  • 시작값이 큰 숫자가 앞에 와야 한다는 건 쉽게 알 수 있습니다. 그렇기 때문에 9와5가 3으로 시작하는 숫자들보다 먼저 오고 있습니다.
  • 문제는 같이 3으로 시작하는 3,30,34를 어떠한 순서로 정렬해야 하는가? 입니다.
    • 조금 더 간단하게 34과 30의 정렬을 생각해 봅시다. 3430과 3034가 가능하며 둘 중 뭐가 앞에오던지 천의자리와 십의자리는 변함이 없고 백의 자리에 의해 대소가 판별되기 때문에 34가 30보다 먼저와야 합니다. 즉 자릿수가 동일할 때에는 큰 숫자가 앞에 와야 더 큰 숫자를 얻을 수 있습니다.
    • 다음으로 3과 30의 정렬을 생각해 봅시다. 330과 303이 가능하며 백의자리만 동일합니다. 30이 먼저 오면 십의자리가 0이 되지만 3이 먼저오면 십의자리가 3이 되어 더 큰수를 얻을 수 있습니다.
      3과 30,31,32,33,34,35,36,37,38,39의 조합을 모두 생각해 봤을 때 3과33은 순서가 관계없으며, 33을 경계로 33 미만의 수는 3이 먼저오는 게 유리. 33 초과의 수는 3이 나중에 오는게 유리합니다. 이 경우에서 우리는 3을 33으로 생각하고 대소를 비교하면 원하는 결과를 얻어낼 수 있습니다.

• 여기까지에서 자릿수가 다르면 자릿수를 동일하게 맞춘 뒤 값을 비교하면 원하는 결과를 얻을 수 있겠구나라는 생각이 듭니다. 이제 자릿수를 어떻게 맞춰야 하는지를 고민해 봅시다. 이번에는 82와 8254를 비교해 봅시다.

  • 앞선 예시에서 3을 33으로 생각해서 옳은 결과를 얻었기 때문에 이와 유사하게 접근해 보려고 합니다.

  • 자릿수를 맞추기 위해 82를 8282또는 8222로 변경하는 걸 떠올렸습니다. 결론적으로 우리는 82를 8282로 만들어 비교하면 원하는 결과를 얻을 수 있습니다. 그 이유는
    82가 앞에 올 때 '8282'54가 생성되기 때문입니다.

  • ab와 abcde를 비교할 때에는 아래와 같은 모양이 되기 대문에 우리는 짧은 ab를 ababa로 만들어 비교를 하면 됩니다.

• 다르게 표현하면 포함되는 숫자(ab)의 첫번째 값(a)과, 포함하는 숫자(abcde)의 포함되는 숫자(ab) 이외의 첫번째 수(c)를 비교한다고 볼 수 있습니다.

• 하지만 두 숫자가 ab와 abade의 형태일 수도 있기 때문에 단순히 하나의 값만 비교하지 않고 긴 값의 길이만큼을 다 비교해 줘야 합니다.

• 문제에서 만들 수 있는 가장 큰 숫자를 문자열로 바꾸어 return하도록 요구했기 때문에 해당 결과는 표준적인 숫자의 형태를 가져야 합니다.

  • 쉽게 얘기해 0009는9로,0000은0으로 표현되어야 합니다.

정답

import java.util.*;
import java.math.BigInteger;
class Solution {
    
    //nums가 1000이하이기 때문에 모든 수를 4자리 숫자로 만들어 줍니다.
    //부족한 칸을 자기자신이 반복되게 채우는 메서드입니다.
    //만약 172이라는 숫자로 7자리 숫자를 만들려면 1721721이 출력되도록 설계한 메서드 입니다.
	static String make_String(String s) {
		StringBuilder sb = new StringBuilder();
		sb.append(s);
		int cnt = 0;
		for (int i = s.length(); i < 4; i++) {
			sb.append(s.charAt(cnt++%s.length())); // 나머지 연산으로 자기자신의 값이 반복적으로 나오게 만들었습니다.
		}
        //다시 원래의 수를 찾기 위해 임의로 붙인 수의 개수만큼 @를 달아줬습니다.
        //12가 들어왔다면 최종적으로 1212@@가 반환됩니다.
		for (int i = s.length(); i < 4; i++) {
			sb.append("@");
		}		
		return sb.toString();
	}
	
    	//make_String으로 인위적으로 늘릴 숫자를 다시 원래대로 되돌리는 메서드 입니다.
    	//make_String으로 만든 값은 "원래 값 + 인위적으로 늘린 값 + 인위적으로 늘린 값의 개수만큼의 @"로 구성되어 있습니다.
    	//"인위적으로 늘린 값 + 인위적으로 늘린 값의 개수만큼의 @"를 제거해 원래값을로 되돌립니다.
	static String remove_dummy(String s){
		int at_count = s.length()-s.replace("@", "").length();//s의 길이 - s에서 @를 제거한 문자열의 길이 = @의 개수
		s = s.substring(0, s.length()-2*at_count);
		return s;
	}
    
    
    public String solution(int[] numbers) {
        // int[]인 numbers를 String[]으로 변환
        String[] arr2 = new String[numbers.length];
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = Integer.toString(numbers[i]);	
        }
        // make_String을 실행한 결과를 담는 배열
        String[] arr3 = new String[numbers.length];
        for (int i = 0; i < arr2.length; i++) {
            arr3[i] =  make_String(arr2[i]);
        }
        // make_String을 실시한 원소들을 내림차순 정렬 
        Arrays.sort(arr3,Collections.reverseOrder()); // 내림차순 정렬

        // 정렬된 순서대로 원래의 값(remove_dummy를 실행한 값)을 하나의 String으로 만듬
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr3.length; i++) {
            sb.append(remove_dummy(arr3[i]));
        }
        
        
        //0000같은 예외적인 경우가 존재하기 때문에 "문자열 -> 숫자 -> 문자열"로 변환하는 과정이 필요합니다.
        //하지만 문자열을 이어붙인 sb.toString()은 너무 큰 값이기 때문에 int와 long에 담기지 않습니다. -> BigInteger사용
        BigInteger numeric_ans = new BigInteger(sb.toString()); //문자열 -> 숫자
        String answer = numeric_ans.toString(); //숫자 -> 문자열
        
        //런타임에러 발생
        //long numeric_ans = Long.parseLong(sb.toString()); // 0000때문에        
        //String answer = Long.toString(numeric_ans);
        

        return answer;
    }
}

기타

• 코드를 다 설계하고 테스트케이스는 통과했는데 채점에서 런타임 에러가 발생해 고생을 했다. 그 이유는 만들어진 숫자가 너무 커서 int나 long에 담기지 않았기 때문이다. 그래서 BigInteger라는 클래스를 사용했다.