프로그래머스 - 가장 큰 수

문제

 

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"

 

문제 접근

 

처음에 내가 접근한 방법은 한자리수는 한자리수 끼리 비교하여 큰수를 앞으로 보내고 두자리수는 두자리수끼리 비교하여 큰수를 앞으로 보내는 방식으로 생각을 했다.

그러나, 내가 생각하는 방식대로 하면 입출력 예 2번에서 문제가 발생한다. 내가 생각한 방식대로 정렬을 실행하면

[3, 30, 34, 5, 9]   -> "9533430" 이 되어야 하지만 문제에서 주어진 입출력 에서는 "9534330"이 리턴값으로 나온다.

 

다른 접근을 생각해 보았다.

배열안에 모든수를 같은 자리수로 만들어서 비교후 정렬하면 어떨까? 라는 생각을 해보았다.

[3, 30, 34, 5, 9] -> [ 33, 30, 34, 55, 99] -> 크기순으로 정렬하면 [ 99, 55, 34, 33, 30 ] 이 되고 이를 원래대로 돌리면

[9, 5, 34, 3, 30] -> "9534330" 이 된다.

 

하지만 이를 코드로 구현하는데 애를 먹어서 결국 정답을 보면서 문제를 복기해보도록 했다.

def solution(numbers):

    num = list(map(str, num))
    num.sort(key = lambda x : x*3, reverse = True)

    return str(int(''.join(num)))

위의 풀이는 int형의 리스트를 map을 사용하여 String으로 만든뒤 리스트로 변환한다.

 

위의 코드에서 lambda x : x*3은 num 인자 각각의 문자열을 3번 반복한다는 뜻이다. 

x*3을 하는 이유는 num의 인수값이 1000 이하이므로 3자리수로 맞춘 뒤, 비교하겠다는 뜻이다.

이 부분이 이 문제의 핵심이라고 할 수 있다.

 

x*2를 하지 않는 이유는 만족하지 않는 경우의 수가 있다. 

예를 들어 [221,2,10]이 주어졌다고 했을떄 x*2를 하면 [221221,22,1010] 이렇게 되면 22보다 221이 문자열 비교해도 더 큰수로 나오기

떄문에 만족하지 않는다. 

마찬가지로 [6, 10, 2] 를 세자리수로 만들어 [666, 101010, 222] 인 상태에서 문자열 비교는 각 자리의 [0]번째 수를 

아스키코드값으로 변환하여 비교를 한다.

6 = 86, 1 = 81, 2 = 82  6 > 2 > 1 순으로 크다. 즉  [6, 2, 10]  => "6210" 이 된다.

 

그리고 위의 코드에서 reverse = True 를 하는 이유는 sort()가 오름차순이기 때문인데

아스키코드 값을 비교했을때 크기 순서대로 오름차순으로 정렬을 하게 되면

[10, 2, 6] 이 되기 떄문에 이를 내림차순으로 변경하면 [6, 2, 10]이 된다.

 

마지막은 join을 통해 문자열을 합쳐주는 것이고

이를 int로 변환한뒤 다시 str로 변환해주는 이유는 모든 값이 0일때를 고려해야 하기 떄문이다.

즉 [0, 0, 0] 일 경우 000을 0으로 출력하려면 int로 만들어준다음 str 으로 변환해야 하기 때문이다.