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

📌 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746

📌 풀이

풀이 1 - (시간 초과)

1. numbers에 주어진 숫자를 가지고 가능한 순열을 모두 만든다.
2. 순열의 조합을 붙여 숫자로 만들어 새로운 리스트에 저장한다.
3. 리스트를 정렬하여 가장 마지막숫자 반환한다.

from itertools import permutations
def solution(numbers):
    answer = ''
    _list= [str(i) for i in numbers]
    nums = [int("".join(i)) for i in (list(permutations(_list, len(_list))))]
    
    nums.sort()
    
    return str(nums[-1])

풀이 2 - (11번 테스트케이스 실패)

itertools.permutations 함수는 입력으로 주어진 리스트의 모든 순열을 생성하는 데 사용된다. 하지만 이 함수는 입력 리스트의 길이에 따라 순열의 개수가 급격하게 증가하기 때문에, 입력 리스트의 크기가 큰 경우에는 연산량이 매우 많아질 수 있다. 따라서 입력 리스트의 길이가 큰 경우에는 시간 초과가 발생할 수 있다. (거저 먹기는 안되네요...🥲)

그래서 정렬을 이용해서 해야한다. 예를 들어 3,30,34가 있을 경우 가장 최대값을 만들기위해서 34, 3, 30으로 정렬되어야 합니다. 문자로 정렬해야 하며 문자로 정렬하면 '34', '30', '3'된다. 여기서 제한 조건을 잘 읽어야한다!! 제한 조건에 숫자는 1000이하라고 했으니 문자를 3번 반복한 문자로 정렬을 해야한다.

def solution(numbers):
    nums =[ str(_) for _ in numbers]
    nums.sort(key= lambda x: x*3, reverse=True)
    
    return "".join(nums)

아깝게도 11번 케이스 실패했다..... 😭

풀이 3 - (성공)

풀이2 코드에서 모든 numbers가 0인 경우에 대해 고려하지 않았다. 예를들어 [0,0,0,0]가 매개변수로 주어졌을때 "0000"이 만들어지고 이를 그대로 반환하게 된다. 이 경우에는 "0"을 반환해야 하기에 추가 조건문으로 예외처리 했다.

def solution(numbers):
    _list = list(map(str, numbers))
    
    _list.sort(key=lambda x: x*3, reverse=True)
    
    # '0'만 여러 번 있는 경우는 예외 처리
    if  _list[0] == '0':
        return '0'
    
    return ''.join(_list)

reference

• permutations함수 정리글
• sort,sorted함수 정리글
• 람다(lambda)함수 정리글