[Python] 프로그래머스 lv.2 가장 큰 수

알고리즘 고득점 kit - 정렬

문제분석

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수 return

 

정답 코드

def solution(numbers):
    numbers_str = [str(num) for num in numbers]  
    numbers_str.sort(key=lambda num: num*3, reverse=True)
    
    return str(int(''.join(numbers_str)))

 

2차 - 2024.12.25

1차 - 시간 초과

• 숫자를 만들 수 있는 경우의 수는 순열?
• 각 숫자를 문자열 처럼 취급해서 붙여서 큰 수를 구하고
• 비교는 정수형으로 바꿔서 비교
• 순서 o, 중복 x → 순열
• 순열로 합해지는 숫자의 조합 생성

from itertools import permutations

def solution(numbers):
    answer = 0
    for r in permutations(numbers, len(numbers)) :
        num = ''
        for s in r :
            num += str(s)
        answer = max(answer, int(num))
    return str(answer)

 

• 모든 조건을 다 계산하면 시간 초과됨

• n개의 요소에 대해 생성되는 순열의 개수는 n!
• n=10: 순열 개수 10!=3,628,800
• n=100,000: 불가능 (100,000!은 계산조차 불가능할 정도로 큼)
• 따라서 입력 크기 제한인 100,000에서는 모든 순열을 생성하는 것은 비현실적이다.

 

• 순열을 생성한 후, 각 순열을 문자열로 변환하고 정수로 변환한 뒤 비교하는 연산이 반복된다.
• 이 연산 자체는 O(n!)O(n!)O(n!)에 비례하므로 매우 비효율적이다.

 

 

2차 - 실패

정답 코드

def solution(numbers):
    numbers = list(map(str, numbers)) # 숫자를 문자열로 변환
    numbers.sort(key=lambda x : x*3, reverse=True)
    answer = ''.join(numbers)
    return '0' if answer[0] == '0' else answer

• 왜 x*3인가?
  • 두 문자열을 비교할 때, 문자열의 길이가 다르면 숫자를 이어 붙였을 때의 대소 관계를 올바르게 비교하기 어렵다.
    따라서 문자열 길이를 늘려서 비교해야한다,
  • ex1) [9, 91]
    • 숫자 9와 91 비교
    • "9" + "91" = "991"
    • "91" + "9" = "919"
    • "991" > "919" 이므로 9가 91보다 앞에 와야 한다.
    • 따라서 문자열 "9"와 "91"의 길이를 맞추기 위해 x*3 사용
      • "9" * 3 = "999"
      • "91" * 3 = "919191"
      • "999" > "919191"
        • 문자열 비교 연산의 경우, 첫번째 인덱스인 "999"에서의 9와 "919191"에서의 1을 아스키 숫자로 바꿔서 비교
          만약 같다면 다음 인덱스 비교한다.
      • 따라서 위와 같은 방식을 사용해야 올바른 비교 결과를 유지한다.
• numbers.sort(key=lamdba x : x*3, reverse=True)
  • key : 각 요소를 정렬 기준으로 변환하는 함수 지정
    • 지정하지 않으면 기본적으로 리스트의 요소 자체를 기준으로 정렬
    • 따라서 각 요소를 정렬하기 전에 변환된 값을 기준으로 정렬하는데
      위 코드에서는 lamdba 함수가 key로 사용
  • lamdba : 익명 함수 정의
    • lamdba x : 입력값 x 를 받고 콜론 뒤에 작성된 표현식 반환