[프로그래머스] 가장 큰 수 - Python

링크

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 합니다.

  ---

실패한 풀이 방법

 

1. 양쪽의 숫자를 합친 숫자를 저장하는 변수 temp1, temp2를 만들어 둘을 버블정렬했다

• 결과: 테스트케이스는 통과했으나 제출시 전부 오답처리됐다...시간 복잡도도 큰 방법이었기 때문에 다른 방법 시도함

2. key=str 방식으로 정렬하면 될 거라고 생각했지만 앞자리는 똑같고 자릿수가 다른 숫자 비교에서 오류 발생

• 1, 1[2], 1[3] / 9, 9[1], 9[2]
• 처음엔 단순히 맨 뒷자리를 반복하면 될거라고 생각해서(← 틀림...) ljust를 사용해서 자릿수를 똑같이 맞추려고 했다
• 이 방법이 틀린 이유
  
  • 테스트 케이스 [401, 40]을 예로 들면 답은 40401이지만 실행 결과는 40140이 나오게 된다(401과 400으로 비교했기 때문)
• 그래서 내린 결론
  • 통째로 반복하자~!!

---

문제 풀이

 

1)코드 설명

    (1) int 리스트 n을 정렬한다

    (2) 리스트의 int형 숫자들을 map 메서드를 이용해서 str형으로 바꿔준다

    (3) 숫자들 중 가장 긴 숫자의 길이를 구해서 maxNum 변수에 저장한다

    (4) 통째로 반복시킨 숫자들을 기준으로 정렬한 뒤, 거꾸로 뒤집는다 (큰 수부터 와야하기 때문)

    (5) 리스트를 한 문자열로 join해서 result 변수에 저장한다

    (6) int(result)가 0(false)이라면 '0'을, 0이 아닌 다른 값이라면 result를 그대로 반환한다

 

2)코드

def solution(n):
    n.sort()
    n = list(map(str, n))
    maxNum = len((n[-1]))
    newArr = sorted(n, key = lambda x : x*(maxNum), reverse=True)
    result = ''.join(newArr)
    return result if int(result) else '0'

 

근데 쓰면서 생각한건데 굳이 maxNum을 이용할 필요가 없는것 같다

제한 조건이 있으니까 자연수를 곱해도 될듯...

• 모범 답안에서 괜히 3을 곱해주는게 아니였다...🥲 여기서는 숫자의 범위가 1 ~ 1000 → 2 자릿수 차이 → 3번을 반복해야 완벽하게 비교를 할 수 있다(범위가 1부터 시작하기 때문에 1000은 상관 없음)
• 만약 1 ~ 10000이었으면 4를 곱해야겠다

 

이 글을 보시는 다른 분들은 자연수를 곱하시길 바라면서,,,ㅎㅎ끝