programmers the Biggest Number

프로그래머스 코딩테스트 연습문제 가장 큰 수를 풀어봤다

가장 큰 수

---

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

---

처음 이 문제를 봤을 때, ‘어 permutation 쓰면 끝이네 개꿀ㅎㅎ’ 이런 생각이 들었다.
바로 itertool을 import 해서

from itertools import permutations
def solution(numbers):
    str_list = []
    for i in numbers:
        str_list.append(str(i))
    first=list(map(''.join, permutations(str_list)))
    int_list = []
    for li in first:
        int_list.append(int(li))
    answer = sorted(int_list, reverse=True)[0]
    return str(answer)

이런 코드를 작성해서 제출했다.

결과는!!

시간초과가 떠 버렸다. 효율성이 제로라는 말이다.
검색해보니 permutation은 필요하지 않은 부분까지 순열 조합을 만들어 내기 때문에
굉장히 비효율적인 코드라는 것을 알아냈다.

‘그렇다면 순열같이 코드를 짜되 효율적으로 작성해야 한다는 것인가?’ 라는 고찰과 함께
코딩을 시작했고 하루를 날렸다.

당연했다. 문제푸는 방향이 완전히 잘못되었었다. 효율적으로 순열조합 만드는 코드를 짠다면 내가 라이브러리를 새로 만드는 수준인 것이었다.

---

방향을 다시 생각해봤다.
사실 이 문제를 풀다보면 list에 있는 원소를 편하게 처리하기 위해 str으로 바꿔야 하고 비교하기 위해
int로 다시 바꿔줘야 하는 번거로움이 있다.

그런데 굳이 int–>str 이런식으로 바꿔줄 필요가 없다.

왜냐하면 정수모양의 str도 정수 값이 증가함에 따라 메모리 값도 증가하기 때문이다.

이를 id()를 통해 확인해 볼 수 있다.

print(id('1'))
print(id('2'))
print(id('3'))
print(id('4'))
print(id('5'))

Out:
4380097928
4380098040
4380111232
4380111288
4379241192

이를 이용해서 문제를 푼다면 다음과 같은 코드를 작성할 수 있다.

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

결론 : 메모리 값에 대한 지식이 있다면, 훨씬 간단하게 문제를 해결할 수 있다!