[프로그래머스] 가장 큰 수 Python (level 2)

TITLE

문제주소 :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 합니다.

 

<풀이법>

▒ 한줄 개념: 원소들 순서 찾기(각 원소 * 3 )▒ 

원소들의 올바른 순서를 찾아서 이어붙여야하는 문제입니다.

그럼 이 ['순서'를 어떻게 찾을 것인가?]를 생각해보아야 합니다.

큰 숫자들이 앞에 위치하고 작은 숫자들이 뒤에 위치하면 될 것입니다.

가장 간단한 방법은 String 원소 * 3을 해서 길이를 늘려주고 정렬하는 것입니다. 왜 그런가?

 

3, 34, 32의 세 숫자를 가지고 순서를 논한다고 해봅시다.

나올 수 있는 순서의 경우는 다음과 같습니다. 

3-34-32, 3-32-34, 34-3-32, 34-32-3, 32-3-34, 32-34-3

가장 큰 수는 34-3-32 순서로 된 34332 일 것입니다.

여기서 중요한 것은 숫자 3은 혼자가 아니라는 것입니다.

34, 32 처럼 3뒤에 어떤 숫자가 붙게 되면 334 또는 332가 될 터이니, 3은 33과 동일하다 볼 수 있다는 것이죠.

따라서 3은 34보다는 뒤에, 32보다는 앞에 위치해야합니다. (34>3>32)

 

쉽게 풀어말하면 다음과 같습니다. 이 문제의 제한 조건에 numbers의 원소는 0~999이므로,

하나의 숫자당 최소 3이상의 길이를 갖도록 동일하게 늘려준다는 것 입니다.

위의 원리에 따라 3 = 333 인 것 처럼 말이죠.

 

파이썬의 자체적인 정렬알고리즘을 사용하면 앞의 숫자부터 차례로 비교하며 정렬해주니,

길이를 3 곱한 원소들(3, 34, 32의 경우 333, 343434, 323232)를 정렬하면 343434 - 333 - 323232 순서로 정렬이됩니다.

 

그럼 원소의 순서를 알게 되었으니, 이 순서대로 original 원소들을 뽑아서 합쳐준다면 원하는 정답을 얻을 수 있게 됩니다.

 

<코드(Python)>

def solution(numbers):
    answer = '' 
    numbers2 = [str(n)*3 for n in numbers] # 한줄 반복문을 통해 모든 원소들의 길이를 3 곱하여 새 배열 생성
    numbers3 = list(enumerate(numbers2)) # 각 원소에 enumerate 함수로 인덱스 붙여줌
    numbers3.sort(key = lambda x:x[1], reverse = True) # 원소들의 값에 따라 정렬
    for index, value in numbers3: # 정렬된 인덱스를 이용해 차례대로 answer 만들기
        answer += str(numbers[index])
        
    return str(int(answer)) # '0000' -> 0 같은 경우를 위하여 int로 한번 바꿔주고 다시 str으로!

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest