문제

링크 - https://programmers.co.kr/learn/courses/30/lessons/42746

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

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

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

풀이

처음에 푼 풀이

from itertools import permutations

def solution(numbers):
    answer = ''
    for i in list(permutations(numbers, len(numbers))):
        result = ""
        for j in i:
            result += str(j)
        if result >= answer:
            answer = result
            
    return answer

처음에 푼 풀이는 좋게 말하면 직관적이게 풀었고 안 좋게 말하면 생각 없이 풀었다. 애초에 문제 카테고리가 정렬인데 그걸 신경도 안 쓰고 내 마음가는대로 풀었다. 당연하게 프로그래머스에서 시간초과가 떴다. 뭐지? 뭐가 문제야? 라고 생각했지만 지금 글을 쓰면서 느끼는 생각은 저렇게 비 효율적으로 코드를 쓰다니 정말 멍청한 사람이구나 라는 느낌이 들었다.

저 문제는 그냥 모든 조합을 다 돌아본 것이다. 모든 경우의 수를 돌아본 것이니 카테고리로 치면 브루트 포스가 아닐까 싶다.

근데 생각해보니까 저기서 이상한 점이 있다.
나는 문자열 (str)형을 마치 숫자처럼 연산을 하고 있다.

if result >= answer:

이 부분이다.

이게 왜 가능한지 간단하게 설명을 해보자. 사실 문자들은 그들만의 순서가 있다. a 가 b 보다 작다. 왜냐하면 저들을 아스키 코드로 바꾸면 a가 더 작기 때문이다.

비슷한 맥락이다. 하지만 자리수가 달라지게 되면 신기한 연산을 하게 된다.
예를 들어, 45 와 446 중에서 정수 체계에서는 446이 더 크다. 하지만 문자열의 세계에서는 45가 형님이다. 왜냐하면 두 번째 자리 숫자가 45가 446보다 더 크기 때문이다.

추가로 한 가지 문제를 내자면 다음과 같다.
Q : 4와 45 중에서 더 큰 숫자는 무엇일까?
A : 45이다. 4는 아래 자리 숫자가 없기 때문이다.

이 개념들을 적용시켜 본 코드는 다음과 같다.

나중에 푼 풀이

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

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

저기 저 람다가 왜 쓰였는지 이해를 해야한다. 44와 443을 비교 했을 때 우리는 44가 더 위로 가길 원한다. 그래야 더 큰 숫자가 나오기 때문이다. 9와 998을 비교했을 때 우리는 9가 위로 가길 원한다. 하지만 9는 아래의 자리 숫자가 없기 때문에 아래로 내려간다. 그것을 방지하기 위함이다. 때문에 원소는 1000보다 작으니까 3번 곱하면 어떤 숫자든 세자리수까지 비교를 하게 된다. 그렇게 하면 정렬을 했을 때 내가 원하는 결과를 얻을 수 있고 그것들을 다시 합쳐주면 정답이 된다.