Programmers / 가장 큰 수 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 가장 큰 수 (2단계)

문제 사이트: 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 합니다.

입출력 예

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

문제를 풀기위해 떠올린 생각들.

 

처음에는 단순히 숫자를 정렬하는 것인가? 라고 생각했는데,

앞자리 숫자가 같은 3, 34, 32, 305 등과 같은 수들을 적절하게 위치를 넣어주어야

가장 큰 수를 만들 수 있다는 것을 깨닳았다.

 

그래서 처음엔, 두자리 수와 한자리 수만 비교를 해보고자 했는데,

만약 리스트에 [3,32,34,8] 이렇게 수가 있으면

8이 가장 앞에 가야 가장 큰 수를 만들 수 있다.

 

단순의 십의 자리수와 일의 자리 수를 비교하려면 각 리스트를 순회하면서 해당리스트의 원소값이 10보다 작으면 10을 곱해서 비교하고, 10보다 크면 그대로 두고 비교를 한다.

 

그렇게 코드를 작성하면

 

def s(arr):
    for i in range(len(arr)):
        if arr[i] <10:
            arr[i] = arr[i] * 10
    return arr
arr = [3,32,34,8]

new_arr = sorted(s(arr), reverse = True)

print(new_arr)

이렇게 출력되는 것을 볼 수 있다. 하지만 이렇게 10을 곱해서 비교하면 앞자리가 8인 수가 가장 크다는 것을 출력을 할 수는 있지만, 나머지 3,34,32 를 이용해서 조합을 할 때 문제가 생긴다. 

 

그렇다고 11을 곱해서 비교를 한다고 하자, 만약 1과 11이 있으면, 1이 10보다 작으므로 11을 곱해주면

1*11 = 11이다. 

11은 10보다 큰 수이므로 그대로 11이다. 따라서 별 차이는 없겠지만, 이러한 연산으로 비교하는 것은 수가 세자리 수 일 때 문제가 생긴다.

 

112과 11을 비교하게 되면, 11은 100보다 작으므로 11을 곱해주게 된다면, 121과 112로 비교를 해야한다.

따라서 문제의 기본적인 가장 큰 수 만들기와 달리 이렇게 비교를 하게 되면 가장 큰 수를 11112로 만들 수 밖에 없게 되는 것이다. (문제의 알고리즘대로 큰 수를 만들면 11211이 만들 수 있는 가장 큰 수이다,)

 

따라서 이 문제는 숫자에 어떤 수를 곱한 값을 기점으로 비교하는 것이 아닌,

숫자를 문자화하여 그 문자를 세 번 반복(문제의 조건이 1000이하의 수이므로, 리스트 원소의 모든 수들을 세자리 수로 만들어서 비교한다.)

 

 

중요 포인트

• str로 형 변환 후, 사전 값으로 배열을 정렬.
• str로 변경한 숫자에 3을 곱한 값으로 재정렬.
• 반환 해줄 때, int로 변환을 해준 후 다시 str로 변경.

3을 곱하는 이유는 2번째 예시를 풀 때 이유를 알게 된다.
계산할 때 사전값으로만 정렬을 한다면 [9,5,34,30,3] 이렇게 정렬된다.
하지만 3이 30보다 앞에 와야한다.
number는 1000이하의 숫자이므로 최대값을 생각해 3을 곱해줬고,
3을 곱하게 되면 [999, 555, 343434, 303030, 333] 이렇게 될 것이고, 정렬을 하게 되면 [999, 555, 343434, 333, 303030]이 된다.

 

최종 풀이

def solution(numbers):
    #0. key point
    numbers_str = [str(num) for num in numbers]               
    #1. 사전 값으로 정렬하기
    numbers_str.sort(key=lambda num: num*3, reverse=True)   
    #2. number는 1000이하의 숫자이므로 x3(반복)한 값으로 비교
    return str(int(''.join(numbers_str))) # 문자열 합쳐서 반환하기

 

 

 

---

※ 알아야 할 것

- lamda: 익명함수로 임의의 변수를 설정하고 해당 변수에 대한 연산을 간단하게 작성할 수 있다.

예제

>>> f = lambda x, y: x + y 

>>> print(f(4, 4)) 

8 

출처: https://offbyone.tistory.com/73 [쉬고 싶은 개발자]

 

- sotred(key = , reverse = True) : Key 값을 기준으로 가장 큰 수 부터 출력

sorted()

 

Prototype

sorted( <list> , key = <function> , reverse = <bool>)
# <list> 뿐 아니라, <Tuple>, <Dictionary>, <Str>에도 사용 가능하다.

• 원본 내용을 바꾸지 않고, 정렬한 값을 반환한다.
• List, tuple, Dictionary, str에 모두 사용 가능하다.
• key 를 통하여 정렬할 기준을 정할 수 있다.
• reverse 가 True이면 내림차순, False이면 오름차순으로 정렬된다.

 

arr = [10, 40, 20, 15]
arr = sorted(arr, reverse = True)
print(arr)

>>>> [40, 20, 15, 10]

sort()

 

Prototype

<list>.sort(key = <function>, reverse = <bool>)

• 원본 자체를 수정한다.
• 반환값은 None
• Tuple , Dictionary, Str 에는 사용이 불가하다.

key값을 사용하면 여러가지 기준으로 정렬을 실행할 수 있다.