[LV 2/정렬] 가장 큰 수

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

프로그래머스

 

[풀이]

---

처음 풀이

from itertools import permutations
def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = list(set(permutations(numbers, len(numbers))))
    numbers = list(map(''.join, numbers))
    numbers = list(map(int, numbers))
    
    return str(max(numbers))

처음 문제 보자마자 푼 풀이는, 시간복잡도 생각하지 않고, 모든 리스트의 값을 다 쓰는 모든 조합을 구한 뒤, 그 중 가장 큰 수를 반환하는 방법이였습니다. 그런데, 시간 초과로 전부 답이 되지 않았습니다.

 

나중 풀이

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x : (x * 4)[:4], reverse = True)
    
    return str(int(''.join(numbers)))

조금 생각해서 정렬을 해야했습니다. 각 수가 있을 때, 3, 31,333, 34의 크기 비교를 어떻게하냐?라고 생각했을 때 처음에는 쉽게 생각이 나지 않았고, 질문 목록을 활용해서 아이디어를 얻었습니다.

• 각 수를 네번 곱한뒤(문자열) 그 문자열을 슬라이싱 해서(네번째까지) 비교 합니다.(제약사항 참고)
• 이렇게 하면 위에서 보여드린 크기 비교가
• 3333, 3131, 3333, 3434
• 이렇게 되면서 정렬은
• 3434, 3333, 3333, 3131 이렇게 됩니다.
• 그러면 34, 33, 3, 31 이렇게 정렬이 되기 때문에 문제에서 원하는 요구사항에 맞춰 정렬 할 수 있습니다.
• 정렬 후 numbers를 모두 합친 후 숫자로 변환하고, 다시 문자열로 변환하는 과정을 통해 제출합니다.

첫번째로 map을 사용한 이유는, 게으른 연산을 통해서 메모리를 절약할 수 있습니다. 즉 계산이 필요할 때까지 연산을 하지 않습니다.

두번째로 lambda는 Heap을 초기화하고, Heap 영역에 할당했기 때문에 함수 종료 시 메모리에서 삭제됩니다. 이를 통해 메모리를 절약하고, 코드를 간결하게 하여 가독성을 높입니다.

세번째로 sort 과정에서 key에 무엇을 넣든 시간 복잡도는 O(nlog(n))입니다. 내부적으로 timsort 알고리즘을 사용합니다.

https://realpython.com/sorting-algorithms-python/#the-timsort-algorithm-in-python

Sorting Algorithms in Python – Real Python

 

[풀이 후기]

---

모든 문제를 완전탐색으로 푸는 습관을 고쳐야겠습니다.. 그래도 문제를 계속 풀고, 이론 공부를 하다보니까 시간복잡도를 왜 생각해야하는지 정도는 이해가 되고 있습니다. 고득점 킷 다음주까지 다 풀어보겠습니당 ㅎㅎㅎㅎ