TIL - algorithm - 배열(1)

문제 설명

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"

풀이

• 이 문제를 처음 접한 대부분은 파이썬의 '정렬' 기능을 활용하여 문제 풀이에 접근해야 함을 금방 눈치챌 수 있을 것이다. 하지만 난관은 그 다음부터 시작된다. 어떤 조건을 기준으로 numbers의 요소를 정렬해야 하는지를 고민해야 하기 때문이다.

• 해결의 실마리는 numbers의 요소를 문자열로 변환하여 사전 순서를 역방향(역 사전순)으로 정렬하는 데 있다. 이러한 방식으로 정렬하면, 정수의 각각의 자릿수를 비교하여, 자릿수의 숫자가 상대적으로 큰 정수를 앞선 순서로 배치하게 된다. 가령 [33, 35]를 문자열로 변환하여 역 사전순, 35의 일의 자리 숫자인 5가 33의 일의 자리 숫자 3보다 크기 때문에, ['35', '33']으로 정렬된다. 코드로 나타내면 다음과 같다.

  • sorted(배열, lambda x : x, reverse=True): 배열의 요소를 역 사전 순서로 정렬한 새로운 배열을 생성한다.

def solution(numbers):
    answer = ''
    numbers_sorted= sorted([str(num) for num in numbers], key=lambda x : x, reverse=True)
    
    for num in numbers_sorted:
        answer += num
        
    return answer

• 매개변수 numbers의 인자로 [6, 10, 2]를 넣고 함수를 실행하면 정렬된 배열 numbers_sorted의 값으로 ['6', '2', '10']이 생성된다. 이 수를 차례대로 이어 붙이기만 하면 문제에서 요구하는 가장 큰 수를 만들 수 있다.

• 하지만 문제가 완전히 해결된 것은 아니다. 경우에 따라서 예외가 발생할 수 있기 때문이다. 이번엔 numbers의 인자로 [3, 30, 34, 5, 9]를 넣고 함수를 실행시켜 보자. 정렬된 배열 값으로 ['9', '5', '34', '30', '3']가 생성되는데, 해당 값에서 '30'과 '3'의 순서가 가장 큰 수를 만들기엔 적절치 않다. 위 배열을 순서대로 모두 연결하면 '9534303'이 만들어지는데, 이는 '30'과 '3'의 순서를 뒤바꿔 연결한 '9534330'보다 작은 값이다.

• 그렇다면 사전식 정렬에서 '3'을 '30'보다 후순위에 배치시키는 방법은 무엇일까? 이 문제를 해결하는 것이 이번 문제의 키포인트다.

  1. 문자열의 길이를 일치시키기

     • 문자열의 길이가 다르면, 문자열 '3'을 그 이상의 수로 증가시키지 않는 이상, '30'보다 앞서 배치될 수밖에 없다. 그러므로 문자열을 추가하여 길이를 일치시키도록 하자.

  2. 문자열의 길이를 일치시키기 위해 같은 문자열 추가하기

     • 이전 문자열과 같은 문자열을 추가하는 이유는, 모든 문자열을 연결하여 가장 큰 수를 만들기 위해서다. 가령 '3'과 '30의 경우, '33'과 '30의 사전적 순서를 비교하는 것 그 예에 해당한다. '30'은 '33'보다 사전식 정렬에서 앞서므로, 결과적으로 '3'을 '30'보다 후 순위로 배치시킬 수 있다.

     • 위 문제의 조건(numbers의 원소는 0 이상 1,000 이하)을 고려해보면, 자릿수가 세자리인 문자열과의 순서를 따지는 경우가 발생할 수 있으므로, 문자열의 길이를 맞추기 위해 같은 문자열을 적어도 세 번은 추가해줘야 한다. 가령 '3'과 '300'의 순서를 비교한다고 가정해보자. 가장 큰 수를 만들기 위해 '3'이 '300'보다 후순위로 배치되야 하므로, '3'을 333으로 바꾼 뒤 '300'과 순서 비교가 이뤄져야 한다.

def solution(numbers):
    answer = ''
    numbers_sorted= sorted([str(num) for num in numbers], key=lambda x : x*3, reverse=True)
    
    # key=lambda x : x*3을 정렬 조건으로 설정하면, 배열의 각각의 요소를 연산 처리(*3)한 뒤 역 사전 순서로 정렬하게 된다.
    
    for num in numbers_sorted:
        answer += num
        
    if int(answer) == 0:
        answer = '0'
        
    return answer

• 마지막으로, 한 번 더 예외 처리를 해줘야 한다. 예외가 발생하는 경우란 numbers의 요소가 모두 0인 경우다. 이 때, 연결된 숫자는 무조건 0이 되기 때므로, answer의 값도 '0'으로 설정해주도록 하자.

reviews

• 배열의 숫자를 이어 붙여 가장 큰 수를 만들기 위해선, 세 가지 조건을 기억해야 한다.

  1. 배열의 숫자를 역 사전 순서로 정렬하자.

  2. 자릿수가 다른 숫자를 비교하는 경우(가령, '5'와 '500')를 고려하여, 문자열의 길이를 맞춰 주자. 이 때, 이전 문자열과 동일한 문자열을 추가하면 된다. 추가하려는 문자열의 길이는... 배열의 요소 값의 범위에 따라 달리진다.(가령 1000이하면 *3을, 100이하면 *2를 해준다.)

  3. 배열 안의 모든 요소가 0(정수)인 경우를 예외 처리하자.