Programmers, 코딩테스트 연습, 스택/큐, ‘가장 큰 수’
프로그래머스 연습문제 중 42746번 ‘가장 큰 수’
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 | return |
|---|---|
| [6, 10, 2] | “6210” |
| [3, 30, 34, 5, 9] | “9534330” |
풀이
Try1
처음 문제에 접근할때는 단순하게 모든 경우를 따져 보면 될것 같아서 itertools 모듈의 permutations으로 문제에 접근했으나 시간초과가 떴다.
이 문제를 접하기 전까지만 해도 파이썬 내부모듈의 효율에 대해 확신을 가지고 있었다.
하지만 검색을 해보니 premutations의 시간 복잡도는 O(n^r)로 알고리즘의 효율을 위해서는 지양해야할 모듈이란걸 알게 되었다.
주어진 numbers를 str로 바꾸고 모든 수열에 대해 최대값을 찾는 식으로 코드를 구현했고, 답을 맞지만 시간초과가 떴다.
from itertools import permutations
def solution(numbers):
max_tmp = 0
candidataes = permutations(map(str,numbers), len(numbers))
# 가능한 모든 경우의 수열에 대해 tmp의 크기를 비교해봄
for candidate in candidataes:
tmp = ''.join(candidate)
max_tmp = max(max_tmp, int(tmp))
return str(max_tmp)
solution([6, 10, 2])
'6210'
시간초과를 해결하기 위해서는 단순 비교하는 하드코딩이 아닌 더 효율적인 방법이 필요했다.
Try2
자바스크립트의 기능 중 sort(compare_func)에 쓰이는 비교함수 compare_func 같은 기능이 파이썬에도 있지 않을까 검색을 , functools의 cmp_to_key 모듈로 javascript의 compare_func과 동일한 방법으로 구현이 가능함을 알게되었다.
cmp_to_key에 대해 간략히 설명하자면 배열에서 차례대로 cmp_to_key(element1, element2)에 두개의 인자가 주어지고, element1과 element2으로 이루어진 return이 True라면 element1과 element2의 위치를 바꾸고 False라면 위치를 바꾸지 않는다.
그리고 수가 0보다 크면 True를 나타내고, 0이거나 0보다 작으면 False를 나타내는 특성을 이용하면 쉽게 비교함수 cmp_to_key를 다룰 수 있다.
이 문제에서는 조합시 더 큰 값을 가지게끔 배열을 정렬해야하므로
def compare(x, y):
tmp1, tmp2 = int(x + y), int(y + x)
return tmp1 - tmp2
과 같이 비교함수를 구현했다.
비교함수를 통해 새로 만든 배열을 맨끝부터 차례로 이어 붙이면 만들 수 있는 최대의 수를 나타낸다.
from functools import cmp_to_key
def solution(numbers):
# 조합했을 때 더 큰값이 가지는 순으로 정렬
def compare(element1, element2):
tmp1, tmp2 = int(element1 + element2), int(element2 + element1)
return tmp1 - tmp2
# sorted의 key=cmp_to_key(비교함수) 인자를 주면 비교함수를 사용할 수 있다.
str_numbers = sorted(map(str, numbers), key=cmp_to_key(compare))
print(str_numbers)
answer = ''
while str_numbers:
answer += str_numbers.pop()
return str(int(answer))
print(solution([9, 8, 98, 89]))
['8', '89', '98', '9']
998898
Leave a comment