[프로그래머스] 가장 큰 수

문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/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 합니다.

 

 

 

📝 풀이

❌ 첫 번째 풀이

def solution(numbers):
    answer = ''
    nums = sorted([[int(str(number)[0]), number] for number in numbers], reverse=True)
    for i in nums:
      answer += str(i[1])
    return answer

 

첫 번째 예제만 보고 가장 앞의 자리 수를 기준으로 정렬한 뒤 붙이면 되지 않을까 했었다.

그러니까 [6, 10, 2]의 예제에 대해서 6, 1, 2를 뽑아내고 이를 내림차순으로 정렬하면 6, 2, 1이 된다.

따라서 이 순으로 원본 숫자를 배치시키면 6210이 된다.

 

하지만 이 풀이는 바로 2번째 예제에서 깨져버렸다.

[3, 30, 34, 5, 9]에 대해서 9534330이 나와야 하지만 9534303이 나오기 때문이다.

 

❌ 두 번째 풀이

def solution(numbers):
    nums = sorted(list(map(str, numbers)), reverse=True)
    
    for i in range(len(nums)-1):
        if nums[i] + nums[i+1] < nums[i+1] + nums[i]:
            nums[i], nums[i+1] = nums[i+1], nums[i]
    
    return str(int(''.join(nums)))

 

일단 1차적으로 string 형태의 숫자들에 대해서 내림차순으로 정렬해준 뒤 해당 리스트를 순회하면서 앞뒤로 합친 문자열들을 비교했다.

그리고 더 큰 수가 나올 수 있도록 순서를 바꿔주었다.

 

이 풀이는 1~6 테스트케이스에서 실패한다.

반례라는 반례는 다 찾아봤지만 모두 결과가 예상한 대로 나오는데 아직 왜 틀리는지 모르겠다.

 

++

반례를 찾았다.

[3, 30, 34, 5, 9, 4, 40, 42]에 대해 954424034330이라는 답을 얻어야 하지만 954244034330이라는 결과를 얻었다.

 

✔️ 세 번째 풀이

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

 

결국 위 방식으로 통과했다.

numbers의 원소가 1000 이하임을 이용한 풀이방법이다.

두 번째 예제인 [3, 30, 34, 5, 9]를 살펴보면 ['333', '303030', '343434', '555', '999']에 대해 정렬을 하게 되는데 문자열에 대한 정렬은 사전순이므로 ['999', '555', '343434', '333', '303030']이 되어 최종적으로 ['9', '5', '34', '3', '30']을 얻을 수 있다.

따라서 해당 결과를 join으로 문자열로 만들어주면 된다.

이때 '0000'과 같은 결과는 0으로 출력하기 위해 nums를 int형으로 바꿨다가 다시 string형으로 변환한다.