[Python] Lv2.가장 큰 수

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

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

나의 접근방법 및 풀이

처음 문제와 입출력 예시를 보며, 위의 그림처럼 주어진 수의 앞자리를 기준으로 정렬해서 만들었다고 생각했다.

그래서 임시 리스트를 만들어 리스트가 비어있다면 첫 번째 수를 그냥 추가하고, 리스트의 길이가 0이 아니라면 들어 있는 수의 앞자리(일의 자리, 십의 자리, 백의 자리, 천의 자리 등)를 비교해서 추가하려는 수가 더 크다면 비교한 수의 위치에 그 값을 추가하는 방식으로 진행해야겠다고 생각했다.

def solution(numbers):
    answer = ''
    tmp = []
    for n in numbers:
        if len(tmp) == 0:
            tmp.append(n)
        else:
            for i in range(len(tmp)):
                count = 0
                if int(str(n)[0]) > int(str(tmp[i])[0]):
                    count = 1 
                    tmp.insert(i, n)                 
            if count == 0:
                tmp.append(n)
                    
    return ''.join(map(str, tmp))

두 번째 for()문에서 if() 문 이용해 추가하려는 수의 앞자리가 비교하는 수보다 크다면 해당 수의 인덱스 위치에 값을 추가하고, count가 0이라면 즉,  tmp에 들어있는 모든 수의 앞자리가 추가하려는 수보다 클경우에는 append를 사용했다.

그 후 최종적으로 join()을 이용해서 tmp에 들어있는 순서대로 합쳤다.

하지만 테스트를 돌리고 생각하지 못한 점을 발견할 수 있었다.

테스트2처럼, 3, 30, 34처럼  앞자리가 같은 경우에는 뒷자리까지 고려해야 한다.

일의 자릿수라면 계속 일의 자리와 다른 수의 뒷자리를 비교해야 하는데 이 점을 생각하지 못했던 것이다.

그리고 만약 이렇게 계속 진행할 경우, 해당 수가 '몇 자릿수'인지도 파악해야 하고 계속 이 점을 반복해야 하는 비효율적(?)인 상황인 발생하는 문제점이 생겼다.

 

다른 사람 풀이

def solution(numbers):
    answer = ''
    tmp = [str(n) for n in numbers]			##1
    tmp.sort(key=lambda x: x*3, reverse=True)		##2
                    	
    return str(int(''.join(tmp)))			##3

그래서 다른 사람의 풀이를 참고했다.

##1. numbers의 값들을 str()로 형 변환하여 tmp리스트에 넣는다.

##2. sort()를 이용해서 tmp를 key에 따라 내림차순으로 정렬한다.

이때 x*3을 기준으로 정렬하는 이유는 numbers의 원소는 0 이상 1,000 이하입니다.라는 제한 사항 때문에, 세 자릿수로 만들어 주기 위하여 문자열을 3번 반복하는 것이다.

이렇게 3번 반복된 문자열을 아스키 값으로 비교하여 정렬한다,

##3. 마지막으로 join()으로 리스트를 합쳐 반환하는데, 이때 str(int())를 하는 이유는 모든 값이 0일 때 ('0000'과 같은) int로 변환하여 '0'으로 만들고 다시 str로 반환한다.