[programmers/ 고득점 kit] 정렬: 가장 큰수

 

이 문제를 풀면서 permutation, compare function 등 여러가지 학습을 할 수 있었다.

결국, 정렬을 위하여 직접 더해본 것을 비교해 봐야함을 알 수 있었다.

여러가지 경우를 다 체크하다 보면 시간이 오래 걸리므로 핵심이 되는 비교의 기준을 잡는 것이 중요했다.

 

입력데이터로 [12,121], [21,212] ,[0,0,0,1000], [20,201] 등 여러 데이터가 있었다. 

최종적으로 테스트 했던 결과를 문제 링크 아래에 첨부해둔다.

 

1. 문제링크

 

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

알고리즘 연습 - 가장 큰 수 | 프로그래머스

2. 테스트 케이스

 

 

3. 소스코드

code :

 

from functools import cmp_to_key
def P(x):
    DEBUG_FLAG = False
    if DEBUG_FLAG:
        print(x)

# final version
def solution(numbers):
    
    lst = []
    # 문자로 변환하여 비교.
    lst = [str(x) for x in numbers]
    # 정렬
    srt_lst = sorted(lst, key = cmp_to_key(compare))
    # 정리 
    answer = "".join([x for x in srt_lst])
    
    # '0000' 처리 위함
    if answer.count('0') == len(answer):
        return '0'
    else:
        return answer

# solve 5 -> solve4 코드 정리한 방법 (이렇게 쉽게 풀린다고?)
# '121' , '12'의 비교를 위해선 직접 더해봐야함.'12112', '12121' 
def compare(x,y):
    if x + y > y + x:
        return -1
    else:
        return 1
#-----------------------------------------------------------------------------------------------------------
# solve 4 -> 211, 21 비교시 2112 , 2122로 만들어서 비교하는 방법을 시행한다. 
# 그 후 값이 같으면 길이가 같을떄만 직접 비교해보는 방법(성공)
# def compare(x, y):
#     if x[1] > y[1] :
#         return -1
#     elif x[1] == y[1]:
#         if x[0]+y[0] > y[0]+x[0]:
#             return -1
#         else:
#             return 1
        
#     else:
#         return 1

#  solution function for solve 4
# def solution(numbers):
#     lst = []
#     for s in [str(x) for x in numbers]:
#         val = s
#         size = len(s)
#         plus_cnt = 4-size
#         for i in range(plus_cnt):
#             val += s[0]
#         lst.append((s,val,size))
#     srt_lst = sorted(lst, key = cmp_to_key(compare))
#     P(lst)
#     P(srt_lst)
#     answer = "".join([x[0] for x in srt_lst])
    
#     if answer.count('0') == len(answer):
#         return '0'
#     else:
#         return answer


#--------------------------------------------------------------------------------------------
#solve 3 -> 0~9를 키로하는 딕셔너리로 나눠서 각각 해결해본 방법(시간초과)
# from functools import cmp_to_key
# def solution(numbers):
#     answer = ''
#     s_list = [str(x) for x in numbers]
    
#     d = {str(x):[] for x in range(10)}
#     for x in s_list:
#         d[x[0]].append(x)
    
#     # print(d)
    
#     for key,value in d.items():
#         d[key] = sorted(value, key = cmp_to_key(compare))
    
#     # print(d)
    
#     answer =[]
#     for i in range(9,-1,-1):
#         answer += d[str(i)]

#     # print(answer)
#     return "".join(answer)

#--------------------------------------------------------------------------------------
# solve 2 -> 스트링 각 원소별로 비교해서 구하는 보조함수 사용 (시간초과)
# def compare(x,y):
    
#     size_x = len(x)-1
#     size_y = len(y)-1
#     i = j = -1
    
#     while True:      
#         if i < size_x :
#             i +=1
#         if j < size_y : 
#             j +=1
        
#         if x[i] > y[j]:
#             return -1
#         elif x[i] < y[j]:
#             return 1
#         else:
#             continue
        
        
        
        
#--------------------------------------------------------------------------------------
# solve 1 -> permutation logic 이용하여 다 구성하는 방법 (시간초과)
# def P(lst):
#     res = []
#     if len(lst) == 1:
#         return lst
#     else:
#         for i in range(len(lst)):
#             other = lst[:i]+lst[i+1:]
#             P_res = P(other)
#             for item in P_res:
#                 res.append(lst[i]+"".join(item))
                
#         return res