[알고리즘]프로그래머스 42746번 - 가장 큰 수

프로그래머스 42746번 - 가장 큰 수

프로그래머스 42746번 - https://programmers.co.kr/learn/courses/30/lessons/42746

 

요구사항

1. 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 바뀌어 반환하라.

 

요구사항 분석 및  풀이과정

1. 직관적으로 생각하면 된다. 예를 들어 6과 10을 붙이는 경우는 "610"과 "106"이다 "610"이 크므로 "610"으로 붙을 수 있게, 6이 10보다 앞에 있도록 정렬을 유지하면 된다.

 

[6, 10, 2]를 대상으로 한번 직접 손으로 해보면 다음과 같습니다.

 

[6, 10, 2] 작동 과정

 

하지만 주의하여할 점이 있다. 결과를 문자열로 변환할 때 수의 왼쪽 첫 번째 자리 숫자가 0으로 시작하는 경우를 문자열로 변환하면 "0xx"가 되는데, 수에서 앞의 0은 아무런 의미가 없기 때문에 "0xx"는 숫자로 xx이고 문자열로 변환할 경우 "xx"가 되어야 한다는 점이다.

 

여기서 이 부분을 처리할 수 있는 방법은 2가지이다.

 

첫째, 수의 앞이 0이 되는 경우를 생각하고 예외 처리를 하여 주는 방법

 

수의 앞이 0이 될 수 있는 경우를 생각해보자. 만약 수의 왼쪽 첫 번째 자리만 0인 경우가 있을 수 있을 까? 그럴 수는 없다. 왜냐하면 수의 두 번째 자리 숫자가 0이 아닐 경우 두 수는 정렬 과정에서 반드시 자리가 바뀔 것이고, 그러면 앞 한자리는 0이 될 수 없다. 

 

그렇다는 의미는 수의 왼쪽 첫 번째 자리가 0인 경우는, 그 수가 '0'으로만 구성된 문자열이라는 의미이고 이는 숫자 0을 의미한다.

그렇기 때문에 변환된 문자열의 1번째 문자가 '0'인 경우는 숫자 0을 문자열로 변환한 "0"을 반환하여 주면 된다.

 

아닌 경우는 문자열 그대로를 반환하여 주면 문제에서 요구하는 결과를 만족시킬 수 있다.

 

둘째, 최종 결과인 문자열로 표현된 수를 다시 수로 변환한 후, 문자열로 변환하여 주는 방법

 

이 방법은 그냥 문자열이 0으로 시작하던지, 수로 변환하는 과정은 라이브러리에 맡기는 방법이다. 문자열을 수로 변환하면, 우리가 원하는 수로 변환이 될 것이고 이를 다시 문자열로 변환하면 문제에서 요구하는 결과를 만족시킬 수 있다.

 

하지만 여기서 중요하게 생각하여할 점은 과연 최종 결과의 수가 어느 범위까지 커질 수 있는가이다. 범위를 예측하여야, 문자열을 어느 자료형의 수로 변환할 것인지 지정이 가능하기 때문이다.

 

이는 문제의 조건을 보면 된다. 정수의 0 이상 1, 000 이하의 값이며, 최소 1개에서 100, 000개가 주어진다고 한다.

 

이 조건으로 정수를 가장 크게 무식하게 붙여보자. 어떤 경우에 가장 크게 붙여질 것 같은가?

 

직관적으로 당신이 생각하는 방법이 맞다. 1, 000이라는 수를 100, 000개 붙이면 된다.

 

"1000" + ... + "1000" (100, 000개를 붙인다.)

 

이때 수의 크기는 간단하게 생각해도 long의 범위를 아득히 넘는 것을 알 수 있다. 그렇기 때문에 수로 변환하고 싶다면 BigInteger을 사용하여야 된다. BigInteger을 사용하여 문자열을 수로 변환한 후, 다시 문자열로 변환하면 문제에서 요구하는 결과를 만족시킬 수 있다.

 

나는 전자의 방법을 택했다.

 

소스코드 작성

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.List;

class Solution {
    
    private int concat2Int(int v1, int v2) {
        int len = v2 == 0 ? 1 : (int)Math.log10(v2) + 1;
        return v1 * (int)Math.pow(10, len) + v2;
    }
    
    public String solution(int[] numbers) {
         
        List<Integer> arr = Arrays.stream(numbers).boxed().collect(Collectors.toList());
        
        Collections.sort(arr, (v1, v2) -> {
            return concat2Int(v2, v1) - concat2Int(v1, v2);
        });

        String result = arr.stream().map(String::valueOf).collect(Collectors.joining());
        return result.charAt(0) == '0' ? "0" : result;
    }
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

두 수를 붙여서 대소 비교를 하기 위해서는 많이 접근하는 방법은 두 수를 각각 문자열로 변환하여 붙이는 방법일 것이다. 하지만 이는 비용이 많이 든다고 생각하였고, 나는 수학적으로 두 수를 붙이는 방법을 택하였고, 그 역할을 하여주는 메서드가 concat2Int 메서드이다.

 

원리는 다음과 같다. v1 + v2를 10진법의 표기하면 다음과 과 같다.

 

'v1' + 'v2'를 정수로 변환한 값 = v1 * 10^(v2의 자릿수) + v2

v2의 자릿수 = floor(log10(v2)) + 1

여기서도 약간의 예외가 존재한다. v2의 자릿수를 구할 때 v2가 0이 되면 안된다는 것인데, v2가 0일 경우는 v2의 자릿수는 1이므로 그 부분을 고려하여 주어야 한다.

 

만약 수학적으로 붙이지 않고 각각 문자열로 변환하여 붙인 경우의 결과는 어떨까? 다음을 참고하자. 그렇게 엄청난 차이를 보이지 않지만 차이가 있는 것을 확인할 수 있다.