[프로그래머스] Level 2_가장 큰 수(정렬)

문제 유형

정렬

 

문제

프로그래머스

 

나의 문제 풀이

1차 시도(26.7, 나머지 시간 초과)

from itertools import permutations

def solution(numbers):
    answer = ''
    str_number = []
    
    num = list(permutations(numbers, len(numbers)))
    
    for i in range(len(num)):
        num_str = list(map(str,num[i]))
        str_number.append(''.join(num_str))
        
    max_num = list(map(int,str_number))
    
    return str(max(max_num))

2차 시도(33.3)

def solution(numbers):
    answer = ''
    str_number = []
    
    num_str = list(map(str,numbers))
    num_str.sort(reverse = True)
        
    
    return ''.join(num_str)

3차 시도(40, 5개 시간초과)

def solution(numbers):
    answer = ''
    list_to_sort = []
    
    # 만약 맨 앞 숫자가 같으면 같은거끼리 다시 큰 수로 정렬한다
    
    # 맨 앞 숫자를 비교해서 큰 수로 정렬한다
    numbers = sorted(list(map(str,numbers)),reverse = True)
    max_num = ''.join(numbers)
    
    for i in range(len(numbers)):
        if numbers[i][0] == numbers[i-1][0]:
            # swap 해보고 join한 것과 안하고 join한거 비교
            numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
            make_num = ''.join(numbers)
            if make_num > max_num:
                max_num = make_num
                    
      return max_num

4차 시도(33.3, 1개 시간초과)

def solution(numbers):
    answer = ''
    list_to_sort = []
    
    # 만약 맨 앞 숫자가 같으면 같은거끼리 다시 큰 수로 정렬한다
    
    # 맨 앞 숫자를 비교해서 큰 수로 정렬한다
    numbers = sorted(list(map(str,numbers)),reverse = True)
    max_num = ''.join(numbers)
    
    for i in range(len(numbers)):
        if numbers[i][0] == numbers[i-1][0] and numbers[i]+'0' == numbers[i-1]:
            # swap 해보고 join한 것과 안하고 join한거 비교
            numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
            make_num = ''.join(numbers)
            if make_num > max_num:
                max_num = make_num
            
            
    
    return max_num

-> 결국 다른 사람의 문제 풀이를 사용

 

다른 사람의 문제풀이

1) 조건 피하기 위해 3배 곱해서 정렬

• 문자열로 변환 후 3을 곱한 값을 역순으로 정렬
  • numbers 원소는 0이상, 1000이하 조건을 피하기 위해 3을 곱함(문자열 곱 ["30"] -> ["303030"]
  • 파이썬 문자열 정렬 : 아스키 코드 값을 기반으로 정렬(숫자의 앞자리가 큰 수부터 정렬)

[프로그래머스] 가장 큰 수(python)

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x : x*3, reverse = True)
    return str(int(''.join(numbers)))

2) functools.cmp_to_key 사용

• cmp_to_key(func) : 정렬함수 key로 함수 전달할 때 사용
  • func(a,b) : a를 기준으로 a,b 비교하고 작으면 -1, 같으면 0, 크면 +1  반환하는 비교 함수 

029 순서대로 좌표를 정렬하려면? ― functools.cmp_to_key

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

리뷰

-  순열을 이용하면 시간복잡도가 커서 시간초과 -> 순열은 사용하지 않는 것이 좋음

[Python] 순열(Permutation)과 조합(Combination) 구하기 - itertools

- 조건을 피해서 만들어보기