3일차, 가장 큰 수

문제

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

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

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

제한사항

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

문제를 보고 든 생각

솔직히 처음에는 좀 쉬워보였다.

이 정도 문제는 풀 수 있을 것 같았다.

정렬 조금 하거나, 조합 돌려가지고 하면 되지 않을까 싶었다.

역시 사람은 누구나 원대한 계획 하나씩은 갖게 되나 보다. 부딪히기 전에는.

결과

from itertools import permutations

def solution(numbers):
    # 순열을 위해 다 문자열로 바꿔주기
    numbers = [str(x) for x in numbers]
    # max값 찾기
    max_number = max([int(x) for x in list(map("".join, permutations(numbers, len(numbers))))])
    return str(max_number)

미리 먼저 풀어보기 단계에서 2문제를 풀기 위한 3시간이 주어졌는데, 이 코드 한 번 제출하고 두 번째 문제는 손도 못댔다.

관리하시는 분이 보시면, 일부러 출석률만 채우려고 이렇게 했나 하고 생각할 수도 있을 것 같다.

정말 저 코드를 제출하고 도저히 다른 방법이 생각이 나질 않았다.

점수는 꼴랑 26.7점 맞았다.

 

그러한 점수의 원인은 정확도는 정상적이었을지 몰라도 순열을 모두 찾는 과정이 시간을 많이 잡아먹는 탓에 [1] * 100만 입력값으로 넣어도 시간이 오래 걸렸다.

문제의 조건은 최대 100,000만까지 입력으로 들어올 수 있는데 말이다.

 

어떻게 풀어야 하는지는 알겠는데, 도대체 어떻게 짜야

9534303이 아닌, 9535330 즉, 3이랑 30을 비교했을 때 3이 더 큰 수라고 판단하도록 만들 수 있는 건지 방법이 떠오르지가 않았다.

 

나중에 알고보니 이게 이 문제의 핵심이었다.

강의에서 배운 것

우선 나의 접근법은 강사분의 접근법과 비슷했고

결국 중요한 건, 3이랑 30을 비교했을 때 3이 더 큰 수라고 판단하도록 어떻게 만드느냐였다.

 

강사님은 문제의 제한사항을 정말 잘 활용하셨다.

문제의 조건 두 번째를 보면, 원소는 무조건 네 자리 수까지만 허용이 된다.

이 점을 문자열에 수가 붙었을 때 값의 크기를 비교할 때 사용하신 거다.

 

그 방법은 아래와 같다.

 

3과 30이 있다고 하자.

이 두 수를 문자열로 변환하여 정렬하게 되면

두 수가 int일 때와 달리 정렬 기준은 두 가지가 된다.

1. 맨 앞자리 수가 누가 더 큰가?

2. 그 뒷자리 수가 누가 더 큰가?

원래 존재하는 두 가지 기준을 내세워서 정렬하게 되면 3보다는 30이 더 큰 수가 된다.

 

하지만, 네 자리 수까지만 허용하므로 이를 이용하여 모든 수를 네 자리로 늘린 다음에 크기를 비교해보는 것이다.

3을 네 자리로 늘리면 3333, 30을 네 자리로 늘리면 3030이 된다.

3333 그리고 3030을 비교하면 3333이 더 큰 수가 된다.

그러므로 3이 더 큰 수라고 판단할 수 있게 되고, 이렇게 판단할 수 있게 만듦으로써 답이 되는 제일 큰 수를 만들 수 있게 되는 것이다.

 

강의를 통해 알게 된 풀이

# 문자열로 바꿔서 sort하면
# 가장 앞 자리의 숫자가 제일 큰 수가 맨 앞으로 온다.
numbers = [str(x) for x in numbers]

# 그런데 정렬할 때 중요한 것은
# 이어붙일 때를 생각해야 한다.
# 숫자 값 상으로 가장 큰 숫자가 만들어져야 한다.

# 3과 30으로 예를 들자면
# 3이 먼저 붙으면 330이 되고
# 30이 먼저 붙으면 303이 된다.
# 그럼 330이 더 크므로 3이 먼저 붙도록 하는 기준을 세워야 하는데
# 그 방법은 숫자를 똑같은 길이로 늘려서 비교하는 것이다.
# 3333 vs 3030
# 3이 더 큰 숫자를 만드므로, 3이 먼저 붙게 되는 기준을 만든 것이다.

# 조건으로 원소가 0이 있을 수 있으므로
# 배열에 0만 있는 상황이라면 00000... 으로 붙게 된다.
# 따라서 이에 방지하여 이러한 상황에는 답을 0으로 출력하도롤 한다.
answer = "".join(sorted(numbers, key=lambda x : (x * 4)[:4], reverse=True))
if answer[0] == "0":
answer = 0
print(answer)

느낀 점

1. 코드 제출 기록을 보니 몇분은 강사분이 알려주셨던 코드와 똑같이 문제를 푸셨다. 나도 언제쯤 그런 문제 해결 능력을 가질 수 있나 싶다.

2. int형의 숫자를 문자열로 변환하고 sort하면 값의 크기를 기준으로 요소가 정렬되는 것이 아닌 맨 앞자리 수의 크기를 기준으로 정렬된다는 걸 처음 알게 되었다.