개발자 아지트

몇일간 못풀던 문제를 풀었다. 속이 후련해야 하는데 이 문제는 속이 시원하면서도 어딘가 찝찝하다;; 

문제설명

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"

문제 해결 방법

1. numbers 요소들을 map함수를 통해 문자열로 변경

2. 0번째 요소부터 바로 다음의 요소를 이용해서
'다음의 요소+현재 보는 요소' , '현재 보는 요소+ 다음의 요소'를 int형으로 변환하여 대소 비교를 한 후 
리스트 index 정렬을 해주었다. 

이때 한자리수에 대한 처리가 어려웠다. 

구체적으로 말하자면 

1. 입력값 [979, 97, 978, 81, 818, 817] 일 때 기댓값 "9799797881881817"인 경우,

2. 입력값 [1000, 111, 110, 101, 100, 11, 10, 1, 0] 일 때 기댓값 "1111111101011010010000"인 경우가 해결이 안되었다. 

문자열을 단순히 복사하여 문자열을 부풀린 후 대소비교는 안하려했으나 이 방법 밖에 풀이가 없는듯 하다. ;;

입력값 81, 818, 817이 있다고 쳤을 때, 문자열로 변환후 정렬을 하면

-> 818, 817, 81으로 나올것이다.  

우선 818, 817의 경우 
818817

817818   두가지 경우가 나올 수 있는데, 818817이 더 크다. 따라서 818, 817의 순서는 자연스럽다. 

817과 81의 경우

81817

81781  두가지 경우가 나올 수 있는데, 중에서 81817이 더 크다. 따라서 현재 817, 81의 순서는 자연스럽지 않다. 

이를 전체적으로 종합해보면 818, 81, 817의 순서가 자연스럽다는 결론을 내릴 수 있다. 

그러나 처음에 818, 81, 817을 문자열로 변환한뒤 정렬한게 818, 817, 81인데,
818, 817, 81 이것을 어떻게 818, 81, 817순으로 정렬할 수 있을까?

두자리 수 인 81을 세자리 수로 만들면서 동시에 817보다는 크고 818보다는 작아야 한다. 

81 뒤에 0부터 시작해서 9까지 어느 수를 붙이든간에 부자연스럽다는 것을 알 수 있다. 

0~7을 붙일경우 817보다 같거나 작게되고, 8을 붙일 경우 818과 같게 되고, 9를 붙이면 818보다 크게 된다.

또한 81이 두자리 수라고해서 다른 숫자를 붙일 경우 다른 숫자들에도 해당 숫자를 붙여주는게 바람직 하다. 

그런데 이렇게 다른 규칙이 없는 임의의 숫자를 정하여 붙이게 되면 숫자의 크기가 어긋나게된다. 

따라서 최선의 방법은 자기 자신을 한번더 자신에게 붙이는 방법이 있다. 

818, 81, 817을 

818818, 8181, 817817 로 한 다음, 
제한 사항에 numbers의 원소는 0이상 1,000 이하라는 사항을 반영하여,

위 원소들을 길이 4로 끊는다.  (3으로 끊어버리면 대소 비교가 어려움--> 818, 818, 817)

8188, 8181, 8178 이때 대소 비교를 하면,
8188 > 8181 > 8178 순으로
818, 81, 817의 순서를 유지할 수 있게된다.

이때, 몇가지 고려해야 할 것들이 있는데, 아래의 테스트케이스를 통해 설명하겠다.

위와같은 논리를 아래에 테스트케이스에 적용한다. 

입력값 〉            [3, 30, 34, 5, 9]
기댓값 〉            "9534330" 에 적용하면

문자열로 변환하여 정렬한다. [9, 5, 34, 30, 3]
9534까지 잘 가다가 330과 303에 걸리게 된다.

303보다 330이 더 크다.  

하지만 이때 3은 한자리수로써, 자기 자신을 한번 더 자신에게 붙여봤자 33이 된다. 

이를 모든 원소에 적용하면

99 55 3434 3030 33이 된다.

이 경우일 때는 결과적으로 정렬에 문제가 없다. 


그러나 다음과 같은 경우에서 문제가 된다.  

입력값 〉           [111, 110, 11, 1]

기댓값 〉           "111111110"

입력값을 문자열로 변환후 2배 해보면

111111

110110

1111

11

대소 비교를 해보면,  111111>1111>110110>11

즉, 111, 11, 110, 1이 된다. 

입력값을 문자열로 변환후 3배 해보면

111111111

110110110

111111

111

대소 비교를 해보면, 111111111>111111>111>110110110

즉, 111, 11, 1, 110이 된다. 

제한사항에 numbers의 원소는 0이상 1,000이하라고 되어있다. 

해당 조건을 고려하여 한자리수 문자열을 위해서 입력값 요소들에 대해 3배로 불리기를 해주고 비교해야 한다. 

코드 구현

def solution(numbers):
    answer = ''

    str_list = list(map(str, numbers))
    str_list.sort(key = lambda x: x*3, reverse=True)
    
    for i in str_list:
        answer+=i

    if int(answer)==0:
        answer = '0'
    
    return answer


# 예전 코드
#     tmp=0
#     i=0
#     while 1:
#         tmp=0
#         if i >= len(str_list)-1:
#             break
            
#         if int(str_list[i]+str_list[i+1]) > int(str_list[i+1]+str_list[i]):
#             pass
                            
#         elif int(str_list[i]+str_list[i+1]) < int(str_list[i+1]+str_list[i]):
#             tmp=str_list[i+1]
#             str_list[i+1]= str_list[i]
#             str_list[i]=tmp
#         i+=1
        
# 참회 코드
#for i in str_list:
#    answer+=str_list[i]
# 완전 잊어먹지 않을 정도로 충격먹음ㅋ
#print(answer)

#print(str_list)

시간/공간 복잡도

O(NlogN)

최적화 및 개선

람다를 쓰면서 코드 최적화를 한 것 같다. 

어려웠던 점

뭐랄까.. 이 문제는 문자열로써의 숫자가 갖는 성질에 대한 이해같다. 

문자를 불려서 해당 값을 비교한다는게 숫자로써의 비교가 아니라 대상으로써의 비교의 연속같다. 

30, 34라는 문자와 3이라는 문자의 비교 같다. 

문자열에는 맨 앞자리[0]가 언제나 큰 우선순위를 갖기때문에 

34가 3434가 되는것이 3이 33밖에 안되는 것 30이 3030이 되는것이 전혀 문제가 되지 않는다. 

즉 숫자 크기로 보면 안되고 오로지 인덱스가 주는 가중치를 생각해야한다. 3은 30보다 커야 하고 그만큼의 가중치를 받아야 한다. 

아 쓰면서도 뭔말인지 좀 살짝 이해하기 어려운데 아무튼 문자열을 하나의 덩이라고 생각하고 덩이끼리 비교한다고 생각한다. 

람다 사용법을 몰라서 생소하고 쓸줄 몰랐다. 

람다는 간략하게 코드 짜고싶을때 사용하기 좋은 것 같다. 

위 코드에서 str_list의 key(원소)들은 lambda 익명 함수의 매개변수 x로써의 역할을 하게된다.