[Programmers] 가장 큰 수 (with Python / 문자열, 정렬)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=python3

프로그래머스

문제설명

 

문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

문제풀이

 

처음에는 다음과 같은 생각을 하였다.

순서 재배치하여 만들 수 있는 가장 큰수 구하기 문제.

 

정렬을 하자
    # => 여러자리수라면 가장 앞자리를 보면 될듯?, 그다음 다음자리수 이렇게

    # 요구사항
    # 1. 숫자가 큰 아이템부터 배치.
    # 2. 숫자가 두자리 수 이상이라면 맨 앞자리부터 비교하여 큰 숫자 부터 배치
    # 3. 한자리수와 두자리수이상의 숫자를 비교할때 같은 방식으로 비교하되,
    #    한자리수가 두자리수이상숫자의 각자릿수 숫자들 보다 한개라도 더 큰게 있다면  (예를 들어 3 vs 30)
    #    한자리수를 먼저 배치.

 

파이썬에서 문자열 대소비교

문자열은 사전순서대로 비교된다.

 

3 vs 30 을 비교한다고 하면

(1) 첫번째 3이 같으므로 다음자릿수로 넘어간다.

(2) 3은 두번째 문자가 없지만, 30은 0 이라는 문자가 있어 30이 더 큰것으로 처리된다.

 

그러나 33과 3030을 비교한다고 하면,

(1) 3이 같으므로 다음자릿수로 넘어감

(2) 3 vs 0 인데 3이 더 크므로 33이 더 큰 문자열인 것으로 처리된다. 

 

핵심

1. 각 배열의 숫자를 문자열로 변환
2. 정렬함수 활용해 내림차순 정렬
3. 이때 각 문자열에 *3을 해주어 길이를 늘린후 정렬.
=> 테스트케이스로 나올 수 있는 원소범위가 1000이하이기 때문에
하지만 1000은 4자리수 아닌가 싶었지만,
하지만 1000은 1이랑 비교해도 3배로 늘린다면
100010001000 vs 111 
=> 111이 더 큰것으로 처리되므로 문제 X

마지막에

int() 변환후 다시 str() 변환해야 테스트케이스 통과됨.

코드

def solution(numbers):
    answer = ''
    
    for i in range(len(numbers)):
        numbers[i] = str(numbers[i])

    numbers.sort(key=lambda x: x*3, reverse=True)
    
    for item in numbers:
        answer += item
   
    return str(int(answer))

 

 

자바스크립트로 풀면

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