오늘 풀이해 볼 문제는 프로그래머스에 있는 레벨2 가장 큰 수라는 문제이다.
프로그래머스 - 가장 큰 수
문제 설명은 간략하게 아래와 같다
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.❓기존 풀이
이 문제를 보고 제일 먼저 떠오른 풀이 방법은 순열을 이용하는 방법이었다.
그 이유는 주어지는 숫자 배열을 이용해 가장 큰 수를 출력하는 거에 초점을 맞추었기 때문이다.
그래서 나는 아래의 순서로 코드를 작성하였다
1. 주어진 배열을 순열(permutation)을 사용해 모든 경우의 수를 만든다.
2. 경우의 수가 담긴 배열에서 제일 큰 숫자를 max를 사용해 뽑는다.
3. 마지막으로 정답을 return할 때 스트링으로 변환해준다.
❓문제점
위의 순서로 작성을 하였는데 해당 방법의 가장 큰 문제점은 두 가지가 있다.
1. 경우의 수가 매우 많을 경우 시간 초과가 발생한다.
2. 예시로 주어진 숫자 배열에 3과 30이 있다면 무조건 30이 크다고 판단할 수 없다.(예외상황)
이러한 문제점이 발생하기 때문에 해당 문제의 초점은 문자에 있다.
애초에 처음부터 주어진 숫자들을 문자열의 배열로 바꾼 후 정렬하는 것이 포인트이다.
정렬 시 lambda를 사용하였고 key=lambda x:x*3 이렇게 정렬을 하였다.
3을 곱해주는 이유는 위에서 예시로 들었던 3과 30의 경우를 생각해보자.
3을 곱한다면 3과 30은 각각 '333'과 '303030'이 될 것이다.
이후 문자열로 정렬을 한다면 '333'을 더 크다고 판단하게 된다.
💡 소스코드
def solution(numbers):
answer = ''
numbers = list(map(str, numbers))
numbers.sort(key=lambda x:x*3, reverse=True)
answer = answer.join(numbers)
return str(int(answer))
👩🏻💻👊🏻⭐️