오늘은 프로그래머스의 '가장 큰 수'를 풀어보았다.
1. 문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
1-1. 제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
2. 나의 풀이
처음 든 생각은 배열의 각 처음 나오는 숫자를 내림차순으로 정렬하는 것이었다. 그렇게 되면 [90, 9, 2] 와 같은 예시를 생각해볼 때 9092가 큰 지 9902가 큰지 비교해줘야 한다.
두번째 생각한 방식은 모든 경우의 수를 만들어 내림차순 정렬하는 것이다. 하지만 이건 효율성 측면에서 좋지않을 것이다.
3. 다른 풀이
다른 풀이는 다음과 같다.
예를 들어, [9, 10]이 있을 때 910 > 109보다 크다. 단순 정렬할 경우 알고리즘은 109를 도출할 것이다. 제한 사항에서 numbers의 원소는 0 이상 1,000 이하라고 명시되어 있다. 따라서 자리수를 똑같이 맞춰준 뒤 비교를 하면 어떤 수가 앞에 와야하는지 알 수 있다.
ex) [12, 121]
각 원소를 반복을 통해 4자리수로 맞춰주면 '1212'와 '1211(21)'이 된다. '1212'가 더 크므로 정답은 '12121'이 된다. 실제로 '12112'보다 큰 수 임을 알 수 있다.
마지막으로 예외사항 한가지가 있다. numbers 원소에 [0, 00]과 같은 경우는 '000'을 산출하게 된다. 따라서 이 예외사항에 대해 '0'으로 정답을 지정해주어야 한다.
코드는 아래와 같다.
def solution(numbers):
numbers = [str(x) for x in numbers]
numbers.sort(key = lambda x: (x*4)[:4], reverse = True)
answer = "".join(numbers) if numbers[0] != "0" else "0"
return answer아무튼
Lv.2인데 나는 어려웠다...
