문제

강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.

0 또는 양의 정수가 주어졌을 때, 정수들을 이어 붙여 만들 수 있는 가장 큰 수 찾기
0 또는 양의 정수가 담긴 배열 : numbers
1 <= numbers의 길이 <= 100,000
각 원소는 0이상 1,000 이하

입출력 예시

접근

모든 경우의 수를 해보면 어떨까.
\(len(numbers)!\) 절대 불가능할 것 같다.

각 숫자의 가장 앞자리 숫자가 크면 먼저 와야 한다.

ex) 9가 30보다 먼저 온다.

앞자리 숫자가 같으면 한자리씩 뒤로 옮기며 똑같이 비교한다. 이때 뒷자리가 없는 경우가 가장 우선순위가 높다.

ex) 9 > 94 > 91 > 90

느낌이 온다. 모든 수를 4자리로 통일해주면 될 것 같았다.
예를 들어 9를 9000으로 94는 9400으로..

결과는 실패했다. 예를 들어, 57과 575가 있을 때,
정답은 ‘57’ + ‘575’ = ‘57575’ 이다.
하지만 위의 방법으론 5700, 5750을 만들고, 5750 > 5700 이기 때문에,
‘575’ + ‘57’ = ‘57557’ 을 만들어 버린다.

4자리를 만들어주는 것은 맞는 것 같다.
만들 때, 0이 아닌 기존 숫자를 반복해서 채워주면 위의 문제를 해결할 수 있을 것 같다.
예를 들어, 57은 5757, 575는 5755 이런 식으로!

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def solution(numbers):
    answer = ''
    l = []
    for number in numbers:
        original = str(number)
        strnum = original
        idx = 0
        while len(strnum) < 4:
            strnum += original[idx]
            idx = (idx + 1) % len(original)
        l.append([strnum, original])
    l.sort(reverse=True)
    if l[0][1] == '0':
        answer = '0'
    else:
        answer = "".join([item[1] for item in l])
    return answer