[프로그래머스 -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 합니다.

입출력 예

해결 아이디어

간단할 줄 알았는데, 생각보다 까다로운 문제였다. 처음에는 각 배열 원소들의 젤 높은 자리의 숫자만 뽑아내서 정렬하면 될 줄 알았는데, 같은 숫자일 경우 순서를 고려해야되는 부분이 까다로웠다. 

 

핵심 아이디어는 두 숫자 a,b의 순서를 정할 때 a+b와 b+a(문자열 연결)를 비교해, 더 큰 쪽이 앞에 오도록 정렬하면 전체가 최대로 된다는 것이다. 이것을 구현하는 방법은 크게 두 가지가 있다. 

 

1. 반복 키 방식: 각 리스트의 원소들을 문자열로 바꾸고, 각 원소들을 3번 반복해서 적어 길이를 맞춰 비교하는 것

2. 직접 비교 함수 방식: a,b를 붙여 만든 a+b와 b+a를 직접 비교하는 방법

 

정답 코드 <Python>

아이디어를 생각해내지 관계로 다른 분들의 풀이를 참고하여 풀었다. 다른 분들의 풀이 중 두 가지를 가져와봤다.

1. 반복 키 방식

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

numbers 배열 안에는 원래 정수가 들어있는데, 문자열을 이어붙이기 위해 map(str, numbers)로 모든 원소를 문자열로 바꿔준다.

핵심 아이디어는 a+b, b+a의 대소를 비교하는 것인데, 이 풀이에서는 x * 3을 이용해서 자리 수가 달라도 비교를 할 수 있도록 문자열을 반복해 길이를 맞춘 뒤 사전순 비교를 하는 것이다.

 sort()함수는 리스트의 각 원소들을 정렬할 때 비교 기준을 필요로 하는데, key인자는 각 원소에서 어떤 값을 뽑아 비교할지를 지정하는 함수이다. 예를들어, key = None, 이고 reverse =  False (오름차순) 이면 기본값으로, 원소 자체를 비교하는 것이다.

만약 원소의 길이를 기준으로 정렬하고 싶다면 key = len 이들어가고, 절댓값 기준으로 정렬하고 싶다면 key = abs, 람다 함수의 리턴값 기준으로 비교하고 싶다면 key = lambda x : x*3 이런식으로 적는 것이다.

 따라서 위 코드는 각 문자열 원소들을 3번씩 반복한 값을 기준으로 오름차순 정렬하고, 그 리스트를 다시 문자열로 이어붙이고, 0이 반복되어 나타나는 것을 방지하기 위해 다시 int로 바꾼 값을 다시 문자열로 변환해준 것이다.

 

2. 직접 비교 함수 방식

import functools

def comparator(a,b):
	t1,t2 = a+b, b+a
    	return (int(t1) > int(t2)) - (int(t1) < int(t2))
    
def solution(numbers):
	n = [str(x) for x in numbers]
    	n = sorted(n, key=functools.cmp_to_key(comparator), reverse = True)
    	return str(int(''.join(n)))

 

조금 더 직관적인 풀이이다. 파이썬의 functools.cmp_to_key를 이용하여 비교 함수를 정렬 키로 사용할 수 있도록 하였다.

 

 

정답 코드 <JavaScript>

1. 반복 키 방식

function solution(numbers){
	let arr = numbers.map(String);
        arr.sort((a,b) => (b.repeat(3)).localeCompare(a.repeat(3)));
        let result = arr.join('');
        return answer[0] === '0' ? '0' : answer;}

 같은 로직이지만 파이썬과의 문법 차이가 있다. 파이썬에서 map(str,numbers) 는 JS에서 numbers.map(String), key = lambda x: x*4는 JS에서 a.repeat(4)와 b.repeat(4)를 localeCompare(문자열 비교) 한다.

 

2. 직접 비교 함수 방식

function solution(numbers){
	var answer = numbers.map(String).sort((a,b) => (b+a) - (a+b)).join ('');
    	return answer [0] === '0'?'0':answer;}