가장 큰 수 2일 차

• 문제 설명
  
  • 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
  • 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
  • 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
• 제한 사항
  
  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

• 실패 문제 풀이
  • 접근을 기존에 100자리 10자리 1자리 다 구하는 식으로 했으나 그렇게 하면 비효율 적이라 그럼 전부 100자리로 만들고 그 걸 기준으로 정렬하기로 결정
  • 그러나 이렇게 했을때 시간에 걸리게 되었다.

def solution(numbers):
    answer = ''
    N = len(numbers)
    temp_dict = {}
    check_dict = {}
    for x,word in enumerate(numbers):
        add_num = str(word)
        if word < 10:
            add_num = str(word * 111)
        elif word > 9 and word < 100:
            add_num = str((word * 10) + (word % 10))
        
        temp_dict[str(word)] = add_num
        if str(word) in check_dict:
            check_dict[str(word)] += 1
        else:
            check_dict[str(word)] = 1
            
    for key, value in sorted(temp_dict.items(), key=lambda x: -int(x[1])):
        for _ in range(check_dict[key]):
            answer += key
    
    return answer if int(answer) > 0 else '0'

 

 

 

• 해당 문제를 풀면서 느낀점
  • 결국 해당 문제를 위해 검색등을 활용하여 다른 사람들이 풀었던 부분으로 확인 해보니 기본적으로 문제 풀이 아이디어는 비슷 했던거 같았다.
  • 시간 복잡도 없이 했다고 하면 양쪽 비교하여 큰 수가 나오는 식으로 만드는데 시간 복잡도를 생각하면 자체 내장 함수들로 이용하여 푸는 식었다.
  • 그중 위의 아이디어와 유사한 부분이 있어서 그부분을 적용 한 코드를 작성하니 간단히 풀리게 되었다.
  • 해당 코드는 간단하게 숫자를 문자로 변경한 걸 배열로 저장 이후 내장된 정렬 함수를 통해 정렬하는데 이때 정렬 기준을 3번 곱했을 때 나온 수로 비교하여 큰수를 앞에 정렬하게 하였다.
  • 여기서 중요한건 제한 조건이 1,000 보다는 작다라는 조건이 들어가기에 숫자들의 자릿수는 3자리이다
  • 그래서 * 3을 하여 자릿수를 3자리로 만들었고 그것을 가지고 정렬을 진행 하면 간단히 끝나게 되는 문제였다

def solution(numbers):
    answer = ''
    str_numbers = [str(number) for number in numbers]
               
    for value in sorted(str_numbers, key=lambda x: x*3, reverse=True):
            answer += value
    
    return answer if int(answer) > 0 else '0'