프로그래머스-가장 큰 수

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

프로그래머스

나의 시도(해결 X)

문제를 보자마자 코드를 만들어 봤는데, 시간초과가 발생했다. 아마도 이중for문 때문에 그런 것 같다.

# 가장 큰 수 구하기
# [6, 10, 2] -> [6102, 6210, 1062, 1026, 2610, 2106] -> 3!개수 -> 6102 (가장 큼)
# 1 <= len(numbers) <= 10만
# 0 <= 원소 <= 1000

# [3, 30, 34, 5, 9] -> 5! -> 120개
from itertools import permutations

def solution(numbers):
    answer = []
    for arr in permutations(numbers, len(numbers)):
        temp = ''
        for i in range(len(arr)):
            temp += str(arr[i])
        answer.append(int(temp))
    return str(max(answer))

 

다른 풀이

이 문제에서의 핵심이 되는 부분은 문자열을 정렬할 때, 사전 순으로 정렬을 하는 것이 핵심이다. 다른 방법도 계속 생각해봤지만, 이 개념을 알고 있었다면 빠르게 풀었을 것 같다.

• 문자열을 정렬할 때 사전순이기 때문에 '1' < '10' < '5' < '6' 이렇게 된다.
• 따라서 아래 코드에서 *3을 한 이유 또한 앞자리수 중복을 막고 완전 구분되게 만들기 위함

# 가장 큰 수 구하기
# [6, 10, 2] -> [6102, 6210, 1062, 1026, 2610, 2106] -> 3!개수 -> 6102 (가장 큼)
# 1 <= len(numbers) <= 10만
# 0 <= 원소 <= 1000
# [3, 30, 34, 5, 9] -> 5! -> 120개

def solution(numbers):
    zeroCount = 0
    for n in numbers:
        if n == 0:
            zeroCount += 1
    if zeroCount == len(numbers):
        return "0"
    
    temp = list(map(str, numbers))
    temp.sort(key = lambda x: x * 3)
    answer = ''
    for i in range(len(temp) - 1, -1, -1):
        answer += temp[i]
    
    return answer