Programmers] 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

[제한 사항]

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

[입출력 예]

 

---

추측)

내림차순으로 정렬하되 같은 첫 숫자로 시작하는 것들 구분이 관건

3이 33이랑은 같지만 34보다 작고 32보다 큼 

끝자리 반복해 더해주고 같은 자리수를 만들고 끝에 끝에자리를 몇번 붙였는지 붙여줌

그 상태로 정렬해주고 끝자리수를 기본으로 해서 붙여준 수만큼 다시 숫자들을 잘라내고 

최종적으로 숫자를 더해주어 처리

 

 

소스코드)

* 1차) 반 이상이 시간초과로 실패 

def solution(numbers):
    answer = ''
    numbers_arr = []
    strNum = ''
    
    for number in numbers :
        strNum = str(number)
        plusNum = 0
        while(number < 1000):
            if number > 1000 : break
            strNum += str(number % 10)
            plusNum += 1
            number = number * 10 + number % 10
        strNum += "*" + str(plusNum) 
        numbers_arr.append(strNum)
        
    numbers_arr.sort()
    numbers_arr.reverse()
    
    for number in numbers_arr :
        answer += number[0:len(number)-int(number[-1])-2]
        
    return answer

 

*2차) 실패 - 11번 뭔데!!!!!!!!!!!!!!

def solution(numbers):
    answer = ''
    numbers_arr = []
    strNum = ''
    
    for number in numbers :
        strNum += str(number)*3
        numbers_arr.append(strNum)
        strNum =""
        
    numbers_arr.sort(reverse=True)
    
    for number in numbers_arr :
        answer += number[0:len(number)//3]
        
    return answer

 

* 3차) 성공 - 11번 케이스는 질문에서 보고 처리 '00000'일때 케이스를 '0'으로 처리

def solution(numbers):
    answer = ''
    numbers_arr = []
    strNum = ''
    
    for number in numbers :
        strNum += str(number)*3             # 한자리 수를 최대값으로 만들때 3번 곱해야 해서 *3
        numbers_arr.append(strNum)          # 배열에 추가
        strNum =''                          # 새로운 숫자를 위해 초기화
        
    numbers_arr.sort(reverse=True)          # 내림차순으로 정렬
    
    for number in numbers_arr :             
        answer += number[:len(number)//3]   # 3번 곱해서 자리수가 얼마만큼 늘어났느냐에 따라 잘라냄
        
    if int(answer) == 0 :                   # 테스트 케이스 11번 : 00000 을 0으로 처리
        answer = '0'
        
    return answer

 

리뷰)

역시 생각했던 부분이 어려웠다.

같은 숫자로 시작하는 것들을 어떻게 비교할 것인지가 중요했던 ㅠ

하지만 문자 경우 숫자와 달리 길이와 상관없이 동일한 위치의 숫자를 문자로 비교하여 더 높은 것을 우선 순위에 놓는다는 것을 깨달았다면 금방 풀 수 있었던 문제였던 거 같다. 제한 사항에 문자열로 바꾸어 return하라는 것도 힌트일지도.

세번 곱해줬던건 1자리 수가 조건인 1000이하에서 최대값을 갖게 해 다른 자리 수들과 비교하게 하기 위해서이다.

2번째 예시에서 보면 3, 30, 34를 비교할때 333, 303030, 343434로 만들어 비교하면 343434, 333, 303030 순서로 정렬된다.