[프로그래머스] 가장 큰 수 정렬문제 python (200713)

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

1. 문제 

 

1)  문제 설명

 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 

 

 

2) 제한 사항

 

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

3) 입출력 예

 

[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

 

2. 풀이 

case 1 : [3, 30, 34, 5, 9]  두자리 숫자까지 나온 경우 

case 2: [999, 9, 998] 세자리 숫자까지 나온 경우 

특이 case : [0,0,0,0] 다 0인경우 

 

 

1) Insertion sort 컨셉 적용해서 풀어봄 (오답)  --> 두자리 까지만 고려함..

def solution(numbers):
    str_numbers = sorted(list(map(str,numbers)),reverse = True)
    for idx in range(len(numbers)-1):
        while (idx > 0) and ((str_numbers[idx][0] == str_numbers[idx+1][0]) and (len(str_numbers[idx]) > len(str_numbers[idx+1]))):
            if str_numbers[idx][1] >= str_numbers[idx+1]:
                pass
            else:
                str_numbers[idx], str_numbers[idx+1] = str_numbers[idx+1], str_numbers[idx]
            idx-=1
    return " ".join(str_numbers)
 

 

이 경우 case 1은 통과가 되지만 case 2는 통과하지 못한다. 

str_numbers[idx][1] >= str_numbers[idx+1] 로 두번째 자리 수만 비교하는 과정이 있기 때문에.  

 

 

 

2) 숫자 반복 후 대소비교 (일부 정답, 접근법은 맞음 ) 

def solution2(numbers):
    str_numbers = sorted(list(map(str, numbers)), reverse=True, key = lambda x:x*3)
    return " ".join(str_numbers)
 

3. 정리 

 

프로그래머스 문제들은 답을 보면 정말 짧고 쉬워서 허무하다. 

뭔가 자료형에 대한 깊은 이해도 필요한 거 같고, 비슷한 문제가 나왔을때 잘 풀어보고 싶다.  

문자형태의 숫자 정렬은 이런식으로 진행되는 것 기억하쟈.!