본문 바로가기

Dev/Algorithm

[Algorithm] 정렬 - 가장 큰 수

programmers에 등록되어있는 정렬 - 가장 큰 수 구하기 알고리즘에 대한 풀이입니다.

개인적인 공부를 위해 작성하는 개인적인 해석으로 경우에 따라 틀린 해석일 수도 있음을 상술합니다.

알고리즘 코딩 테스트는 간편하고 빠르게 구현할 수 있는 언어인 파이썬으로 응시하는 경향이 강하다고 합니다.

따라서 알고리즘 포스팅 또한 파이썬을 기준으로 풀어보도록 하겠습니다.

 

코드 링크는 아래 첨부합니다.

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

 

본격적인 포스팅을 하기에 앞서 일러두자면, 후술 할 설명들은 최대한 자세하게 코드의 흐름을 설명하고자 하였으므로, 숙달된 분들에게는 불필요한 서술이 많습니다.

만약 코드 자체만으로 분석이 가능하신 분들은 위에서 두 번째마지막 코드 블럭만 참고하시면 됩니다.

 

설명하기에 앞서, 알고리즘 문제에 대한 설명 전문을 첨부합니다.

문제 설명

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 commands
[6, 10, 2] "6210"
[3, 30, 34, 5, 9] "9534330"

 

 

그리고 위 설명을 풀이하기 위한 디폴트 코드는 아래와 같습니다.

 

def solution(numbers):
    answer = ''
    return answer

 

solution 함수는 numbers라는 배열을 매개변수로 받고 있습니다.

이 문제의 핵심은 주어진 정수들의 순서를 조합해 나올 수 있는 가장 큰 수를 뽑아내는 것입니다.

 

문제 설명에 의하면 numbers라는 객체는 1개 ~ 100000개 이하의 정수 형 배열이 입력됩니다.

또한 배열 구성 요소는 0이 올 수도 있고 1000 이하의 숫자가 올 수도 있습니다.

먼저, 입력받는 정수의 상한선이 1000 이하 임을 인지해주세요.

 

이 문제는 숫자가 크다고 무조건 앞쪽에 배치되어서는 안 됩니다.

이를테면 [30, 9]라는 배열이 들어왔을 때, 30이라는 숫자가 크다고 309 형태로 반환해서는 안된다라는 의미입니다.

이 경우, 두 수를 조합해 뽑아낼 수 있는 가장 큰 수는 930입니다.

즉, 숫자를 단순 비교하는 방식으로는 올바른 답을 도출할 수 없다는 의미입니다.

그렇다면 이 문제를 어떻게 해결할 수 있을까요?

 

여러 가지 방법이 있겠지만 제가 선택한 방법은 바로, 각 숫자에 부여된 아스키코드값을 비교하는 것입니다.

아스키코드값은 문자의 경우 a - Z 순으로 코드값이 증가합니다.

숫자도 0 - 9 순으로 코드값이 증가하죠.

예시에서 언급한 [30, 9] 값이 들어왔을 때를 가정하고, 각 숫자의 아스키코드값을 비교해봅시다.

정수 아스키 코드값
30 51 48
9 57

 

위 표를 보면, 정수로 봤을 때는 30이 9보다 크지만 아스키 코드값을 봤을때는 9가 더 높은 인덱스에 할당되어있음을 알 수 있습니다.

이를 이용하면 어떤 숫자가 먼저 배치되어야 가장 큰 숫자로 조합이 가능한지 감이 잡힙니다.

이 아스키코드를 구하기 위해서는 숫자를 문자로 바꿔야 할 필요가 있습니다.

 

이 문제에 대한 알고리즘의 순서는 아래와 같습니다.

(옵션) 주어진 numbers의 정수 값 중 가장 큰 수의 문자열 형태일 때의 길이를 구한다.

1. 입력받은 numbers 배열을 문자형태의 배열로 변환한다.

2. 아스키코드 값을 기준 내림차순 정렬한다.

3. 배열의 각 요소를 문자열 형태로 조합한다.

 

위 알고리즘에 근거한 제 코드 풀이는 아래와 같습니다.

def solution(numbers):
    answer = []
    
    #문자열 배열로 변환한다.
    nbs = list(map(str, numbers))
    
    #각 문자열로 변환된 아스키 코드 * 3 값을 기준으로 내림 차순 정렬한다.
    nbs.sort(key=lambda x : x * 3, reverse=True)

    #정렬된 배열을 문자열로 조합한다.
    answer = str(int(''.join(nbs)))
        
    return answer

 

위에서 언급한 (옵션)을 제외했을 때의 완성할 수 있는 코드입니다.

이번 알고리즘은 절차가 많지 않으므로 위 코드를 기준으로 해석하겠습니다.

 

이전 포스팅에서 언급한 map을 이용하면 반복 가능한 변수를 특정 논리를 거쳐 어떠한 결과 값을 받을 수 있다고 이야기했습니다.

위 코드에서 가장 처음 작성된 코드는 아래와 같습니다.

list(map(str, numbers))

이는 numbers 배열의 각 요소를 str(문자열) 형태로 변환한 것을 배열로 반환하라는 의미가 됩니다.

다음은 문자열의 아스키코드값 비교입니다.

nbs.sort(key=lambda x : x * 3, reverse=True)

sort 함수와 익명 함수 lambda식이 사용되었습니다.

여기서 사용된 sort 함수의 구조는 sort(정렬 값 기준, 정렬 방향)으로 이해하시면 되겠습니다.

사용된 람다식은 각 문자열의 아스키코드 값을 비교해 이를 기준으로 삼겠다는 의미로 작성되었습니다.

 

그런데 의문을 가질만한 부분이 있습니다.

바로 x * 3 이 부분인데요, 왜 아스키코드 값을 비교하는데 3을 곱하는 부분이 존재할까요?

이는 아스키코드값의 자릿수를 맞춰주기 위함입니다.

서두에 정수의 상한선이 1000 이하 임을 인지해 달라고 당부드린 부분과 연관이 있습니다.

 

 

만약, x * 3이 아니고 이보다 적은 x * 2를 적용하게 되면 어떤 일이 벌어질까요?

그림을 통해 확인해보겠습니다.

예시에서의 number 값은 [330, 3, 31, 331]으로 가정합니다.

x * 2 일 때의 결괏값
x * 3일 때의 결괏값

sort 함수에서 아스키 코드값을 비교 할 때는 첫 번째 열이 동일 할 경우, 두 번째 열의 값을 비교, 두 번째 열의 값도 동일 할 경우 세 번째 값을 비교합니다.

따라서 위와 같은 결괏값이 도출됩니다.

 

그런데, x * 2 일 때와 x * 3일 때의 결괏값이 다름을 알 수 있습니다.

x * 2와 x * 3의 결괏값 차이는 1793700입니다. ( x * 3의 결괏값이 더 큼)

차이가 나는 이유는, 각 값들의 자릿수 비교에 있습니다.

주어진 값의 3과 331을 비교했을 때, 만약 x * 2를 했다면 3은 33이 되지만 331은 331331이 됩니다.

3이라는 숫자는 x * 2를 한다 해도 배열 내 최대 자릿수를 보유한 331의 자릿수에 미치지 못하기 때문에 무조건 331 보다 뒤쪽에 위치하게 됩니다.

이는 앞 한 자리 ~ 두 자리 숫자가 같은 숫자끼리의 비교는 단순 숫자비교와 다를 것이 없게 되므로 의도하지 않은 결괏값을 도출하게 됩니다.

 

즉, 작은 숫자든 큰 숫자든 동일한 자릿수 선상에서 값을 정렬하기 위해 가장 큰 숫자의 길이 만큼 x * 3을 사용한 것입니다.

 

만약 1000 이상의 숫자까지 지문에서 허용할 경우, 맞춰줘야 할 자릿수는 x * 4가 되어야 올바른 비교가 가능합니다.

그다음 sort함수의 매개 변수에 선언되어있는 reverse=True 구문에 의해 내림차순으로 정렬된 후, 문자열로 조합해 반환하면 문제애 대한 해답을 만족할 수 있습니다.

 

(선택)

다만, 위 코드에서 생기는 불만사항이 있을 수 있습니다.

지문에서는 제시되지 않았지만, 주어지는 numbers의 값이 세 자릿수, 네 자릿수 등이 올 경우에도 대응할 수 있는 코드를 작성하고 싶을 수 있습니다.

그럴 때는 아래와 같은 코드를 적용합니다.

def solution(numbers):
    answer = ''
    
    #가장 큰 숫자를 문자열로 변환, 그 길이를 구한다.
    #정수 20의 문자열로 변환 했을 때 길이 = 2
    max_char_len = len(str(max(numbers)))
    
    nbs = list(map(str, numbers))
    
    nbs.sort(key=lambda x : x * (max_char_len), reverse=True)
    answer = str(int(''.join(nbs)))
    return answer

max 함수를 통해 숫자로 된 배열중 가장 큰 수를 구하고, 이를 문자열로 변환합니다.

그리고 해당 문자열의 길이를 max_char_len에 적용한 다음 sort함수 내 람다식에 대입해 줍니다.

만약 1000이 배열 내 가장 큰 수라면 max_char_len은 4가 될 것이고, 100이 가장 큰 수라면 3이 되는 등, 주어진 배열의 값에 따라 유동적으로 적용할 수 있습니다.

 

(번외)

본 예시에서는 정렬에 sort() 함수를 사용했지만, 또 다른 정렬 함수인 sorted()를 사용해서 정렬하는 것도 가능합니다.

다만, sorted() 함수는 원래 변수를 갱신하는 것이 아닌 새로운 변수를 생성하므로 sorted() 변수에 의한 결괏값을 변수에 지정해 주어야 합니다.

sorted() 함수의 적용 예시는 아래와 같습니다.

 

def solution(numbers):
    answer = ''
    max_char_len = len(str(max(numbers)))
    
    nbs = list(map(str, numbers))
    
    nbs = sorted(nbs, key=lambda x : x * (max_char_len) , reverse=True);
    
    answer = str(int(''.join(nbs)))
    return answer

사용된 sorted() 함수의 매개 변수 구조는 아래와 같습니다.

sorted(순환 가능한 변수, 정렬 기준. 정렬 방향)

 

numbers는 재활용되지 않고 딱 한 번만 연산에 사용되기 때문에 연산을 마친 이후에는 필요 없는 변수가 됩니다.

따라서 데이터를 복제해서 새롭게 값을 저장하는 sorted보다는 sort 함수를 사용하는 게 다소 효율적일 수 있습니다.

(sort 함수는 기능 수행 후, 본래의 변수의 저장 값을 수정합니다.)

'Dev > Algorithm' 카테고리의 다른 글

[Algorithm] 선택, 삽입, 버블 정렬  (0) 2021.04.24
[Algorithm] 에라토스테네스의 체  (0) 2021.04.24
[Algorithm] Binary Search(이진 탐색)  (0) 2020.09.17
[Algorithm] 정렬 - K번째 수  (0) 2020.08.17