프로그래머스 '가장 큰수'

문제 링크 및 문제 내용

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

입출력 예

※ 공지 - 2021년 10월 20일 테스트케이스가 추가되었습니다.

풀이 코드👌

# 가장큰수
def solution(numbers):
    # int-> str 변환
    numbers = list(map(str, numbers))
    # * 람다함수를 사용해서 666, 101010, 222 일때 첫번째 인덱스 값의 내림차순으로 정렬
    # 이유 -> 3, 300 일때 333, 300300300 -> 이렇게 되서 300이 뒤로 가게 할 수 있다.
    numbers.sort(key=lambda x: x * 3, reverse=True)
    # int로 한번 변환 해주는 이유는 모든 값이 0일때 0으로 변환해주려함
    return str(int(''.join(numbers)))

실패한 풀이😂

from itertools import permutations
import re
def solution(numbers):
    result = [0]  # 저장값 리스트
    comAn = list(permutations(numbers ,len(numbers))) # 순열로 경우의수 도출
    for com in comAn: # 경우의수를 반복하며 숫자 처리해주고, 큰수 일때만 넣어줌.
        com = re.sub('[^0-9]','', str(com))
        if result[-1] < int(com):
            result.append(int(com))
    return str(max(result))

이렇게 풀었어요🔍

  1. 경우의 수를 순열로 도출하자. → 시간 초과 → 인덱스를 통한 정렬
  2. 경우의 수를 반복해서 큰 수 찾아내기 → 시간초과

발생했던 문제점🤣

애초에 순열로 시작을 하면 안되는 문제였습니다..

간단하게 람다 함수를 통해 구할 수 있었는데, 가장 중요한 부분을 설명 드리려고 해요.

처음 작성했던 람다식입니다.

# 처음 람다식 작성했을때
numbers.sort(key=lambda x:(x[0], x, reverse=True)

numbers = [3, 30, 34, 5, 9] 일 때 위의 식의 경우에는 9534330이 아니라 9534303 이 나오게 됩니다.

첫번쨰 인덱스의 크기로 정렬하고, 이후 크기순으로 정렬했기 때문이고, 이후 람다식으로 풀 수 없겠다는 생각이 들어 순열로 갔습니다ㅠㅠ

이 후 참고 했던 코드입니다.

# x * 3을 해준 이유는 number는 0 ~ 1000의 크기의 수이기 때문입니다.
numbers.sort(key=lambda x: x * 3, reverse=True)

위의 경우에는 같은 3, 30 의 경우 333 300300300 의 경우가 되기 때문에 3 이 앞으로 오게 만들 수 있었습니다.

좋은 웹페이지 즐겨찾기