[프로그래머스 LV.2] 가장 큰 수 (python 풀이, 시간 초과 해결)

 

가장 큰 수 

 

알고리즘 고득점 kit 정렬 카테고리에 있는 문제이다 

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

프로그래머스

 

문제 풀이 방법은 numbers안에 있는 걸 문자로 바꾼다음에, 각각 숫자들을 만들어서 가장 큰 값을 꺼내오면 된다고 생각했다. 

그래서 써야할 것이 무엇이 있을까에 대해서 고민 !

일단 순열을 써서 나올 수 있는 문자들을 만들어야 하니까 permutations을 사용, 

그리고 map()이랑 max()정도를 생각했다. 

 

 

 

처음 생각한 풀이 (시간 초과 )

 

 

풀이 )

from itertools import permutations
def solution(numbers):
    answer = ''
    num=permutations(map(str,numbers),len(numbers))
    
    # 순열 리스트를 숫자로 변환
    max_number = max("".join(p) for p in num)
    
    return max_number

 

 

1.map()

map(str, numbers)

숫자 리스트를 문자열 리스트로 변환 (예: [3, 30, 34, 5, 9] → ['3', '30', '34', '5', '9'])

 

2. pemutations()

permutations(map(str, numbers), len(numbers))을 사용해서 모든 가능한 숫자 조합을 만듦

 ['3', '30', '34'] → ['33034', '33430', '30343', ...]

 

3. "".join(p) 

각 순열을 하나의 문자열로 결합하여 숫자로 변환

('3', '30', '34') → "33034"

 

4.  max() 

모든 가능한 조합 중 가장 큰 값을 찾음

 

 

이렇게 사용해서 문제를 해결~한줄 알았지만

++ 테스트 케이스 통과는 했는데 문제 제출에서 시간 초과가 걸림.. 그럴만도,,,,,,,,,,ㅠ

 

허허 오늘도 쓰레기 코드를 만들어버렸다 

 

아무래도 순열을 사용해서 시간 복잡도가 O(N!) 이라서 그런거 같다..

순열을 다 안돌아도 되는 방법에 대해서 생각을 해보쟝쟈쟈쟈

 

 

최적화 (더 빠르고 옳은 풀이 )

다른 방법이 뭐가 있을까 고민하다가 찾아보니 순열을 다 안돌아도 되는 정렬 방법이 있었다.

시간 복잡도도  훨씬 좋다. 이 방법은 O(N log N)으로 위의 코드보다 빠름

 

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)  
    
    return str(int("".join(numbers)))  # 000 같은 경우 방지

 

 

numbers.sort(key=lambda x: x*3, reverse=True):

문자열을 세 번 반복한 값을 기준으로 정렬

 ['3', '30', '34'] → ['34', '3', '30']

 

"".join(numbers):

리스트를 하나의 문자열로 결합

 

str(int(...)):

"000" 같은 경우를 방지하기 위해 int() 변환 후 다시 str() 변환

 

 

이런 방법을 바로 생각해 내도록 아자자