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

❓ 문제

문제 설명
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를 사전 순으로 sort해 주어야 하며 큰 수부터 문자열에 붙어야 하기 때문에 reverse=True 처리를 해 준다.
• 마지막 테스트 케이스에서 계속 오류가 났는데 만약 numbers가 모두 0인 [0, 0, 0, 0]과 같은 리스트가 들어온다면 0으로 합쳐 주어야 하지만 문자열로 0을 붙일 경우 0000이라는 결과가 나온다. 그렇기 때문에 0일 경우 0이 나오도록 if문으로 통해 따로 처리해 주어야 한다.

def solution(numbers):

    answer = ''
    numbers.sort(reverse=True, key = lambda x : str(x)*3)
    
    if numbers[0] == 0:
        return "0"
    
    answer = ''.join(list(str(x) for x in numbers))
        
    return answer

❕ 다른 사람의 풀이

• O(nlogn)만큼의 시간이 소요되는 알고리즘

def solution(numbers):
	numbers = [str(x) for x in numbers]  #numbers를 다 돌기 때문에 O(n)
    numbers.sort(key = lambda x: (x * 4)[:4], reverse=True)   #정렬 알고리즘을 쓰면 O(nlogn) 
    if numbers[0] == '0:
    	answer = '0'
    else:
    	answer = ''.join(numbers)    #numbers에 들어 있는 원소의 개수에 비례 O(n)
    return answer