[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/42746
📌문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
💡 문제 풀이
주어진 입력값(numbers)의 원소들의 특징을 파악한 후 적절히 정렬하면 쉽게 풀 수 있는 문제
문제를 읽고난 후 본능적으로 순열을 사용해야하는 줄 알았다.
원소들의 타입을 변경(string ↔ int)하면서 최대값을 금방 찾았지만 '시간초과'로 인하여 실패!
이후 다양한 시행착오 끝에 문제를 해결한 방법은 다음과 같다.
'제한사항'을 보면 numbers의 원소 범위는 0이상 1,000이하다.
즉, 숫자의 길이는 1 ~ 4까지이다.
이 점을 착안하여, 좀 더 탐욕스럽게(?) 접근했을 때
앞 자리수부터(왼쪽부터) 가장 큰 숫자를 우선적으로 배치하는 것이 가장 큰 수를 만드는 방법임을 알 수 있다.
ex) 두 번째 예시 [3, 30, 34, 5, 9]에서 가장 큰 수는 9534330이다.
→ [9, 5, 3, 34, 30] 순으로 정렬
문제 풀이의 순서는 다음과 같다.
step 1)
numbers 원소들의 숫자 길이가 항상 같지 않기 때문에 비교하기 위해서는 길이를 통일시켜야할 필요가 있다.
이를 위해 numbers의 원소들을 string 타입으로 변환시켰다.
step 2)
숫자의 길이는 1 ~ 4까지다.
어떠한 숫자의 길이가 나와도 동일한 크기로 비교하기 위해서는 최소공배수(12)에 해당하는 길이로 맞춰줘야한다.
따라서, 원소들의 기존 길이를 고려하여 12의 길이를 가질 수 있도록 값을 늘린다.
ex) 5 → 555555555555 / 34 → 343434343434 / 352 → 352352352352
길이를 통일시키더라도 기존의 값이 무엇인지는 알아야 하기 때문에
(원래 값, 12의 길이로 변형한 값) 형태로 배열에 담는다.
- same_length : (원래 값, 변형한 값(길이 12)) 튜플을 담는 배열
step 3)
이제 동일한 길이이기 때문에 대소 비교가 가능하다. 변형한 값(길이 12)을 기준으로 오름차순 정렬을 한다.
ex) 3과 30이 있다고 했을 때 각각 아래와 같이 변형이 된다.
333333333333 / 303030303030
왼쪽부터 같은 인덱스의 값으로 대소비교를 하게 되면 333333333333이 더 크다는 것을 알 수 있다.
따라서, 큰 수를 만들기 위해서는 '3'이 '30'보다 우선해야한다는 것을 알 수 있다.
step 4)
정렬한 same_length에 대해 가장 왼쪽부터(= 가장 큰 값부터) '원래 값'을 answer 변수에 더한다.
이후 형변환을 한 번 거친 후 answer 값을 return 한다.
※형변환을 거치는 이유(반례)
numbers = [0, 0, 0, 0]으로 주어질 경우 정답은 '0'이 되어야 한다.
하지만 단순히 문자열을 더한 answer를 return하게 되면 '0000'의 문자가 되므로 int → string 형 변환이 필요하다.
코드는 다음과 같다.
def solution(numbers):
answer = ''
strnum = list(map(str, numbers))
same_length = [[i, i * (12//len(i)) ] for i in strnum]
same_length.sort(key=lambda x:x[1], reverse=True)
for i in same_length:answer += i[0]
answer = str(int(answer))
return answer