[알고리즘/정렬] 프로그래머스 가장 큰 수

4. 프로그래머스 가장 큰 수 

문제

코딩테스트 연습 - 가장 큰 수

 

문제 설명

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"

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 자릿 수의 가장 앞에 오는 수가 가장 큰 것대로 정렬 해야 한다.

 

고려 사항

• 3과 30 을 비교하는 예를 들어보면, 두번째 자리를 비교해야 하지만 3은 한 자리 수이다. 어떻게 비교할 것인가?
  • 3과 30,31,32에 대해서 비교하면 3이 앞에 나와야 하지만, 33 이후의 34부터는 34가 앞으로 나와야 큰 수를 만들 수 있다.
  • 따라서 3이라는 숫자와 30을 비교할 때는, 3을 33으로 바꾸어 33과 30을 비교하면 간단하다.
  • 이 방법을 통해, 수가 1,000이하라는 점을 고려해 각 수를 문자열로 바꾼 뒤 문자열의 길이의 3배만큼 곱하여 서로 비교할 수 있도록 만든다.

---

작성 코드

def solution(numbers):
    arr = [str(n)*3 for n in numbers]
    result = ""
    arr.sort(reverse=True)
    for a in arr:
        for i in range(int(len(a)/3)):
            result += a[i]

    return str(int(result))

def main():
    print(solution([6,10,2]))
    print(solution([3,30,34,5,9]))
    print(solution([30,300,303,330,333,3,33]))
    
    
main()

 

 

---

답안 코드

• 문자열을 3번 곱한 것을 내림차순으로 정렬하고 각 리스트의 요소들을 이어붙인 것을 출력한다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

 

리뷰 및 점검

• 문제의 조건 중 numbers의 원소가 0 이상, 1,000 이하라는 점을 유의해서 보았어야 한다.
• 문제를 구현하는 것은 쉬웠으나, 3번 곱한다는 아이디어를 얻는데까지 오랜 시간이 걸렸다.