[프로그래머스/Level2] 가장 큰 수

문제 설명

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"

---

나의 풀이 

[Python(파이썬)]

def solution(numbers):

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

 

---

학습한 내용

※ 체크 할 내용

- 정답은 문자열로 바꾸어 return 

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

- numbers의 원소는 0 이상 1,000 이하

 

풀이 과정
1. 제일 앞자리 숫자를 비교해서 나열?
2. 같은 숫자일 땐 뒤에 숫자를 비교?

 

1. 제일 앞자리 숫자를 비교해서 나열?

 

리스트를 문자열로 바꿔서 비교하면 제일 앞자리를 비교해서 나열한다. 

그래서 max()를 이용해 문자열 앞자리를 비교하는 코딩을 했다.

numbers = list(map(str, numbers))

for j in range(len(numbers)):
    answer += numbers.pop(numbers.index(max(numbers)))

하지만 이 코드는 2번과 같은 문제가 발생했다. 

 

 

2. 같은 숫자일 땐 뒤에 숫자를 비교?

ex) 3, 30 일때 303보다는 330이 더 큰 숫자가 될 수 있다. 

1번의 코드는 330이 안나오고 303이 나온다.

 

그래서 그 문제를 해결하기 위해 permutation을 사용한 후 가장 큰 숫자를 선택하는 코드를 만들었다. 

# 시간 초과 코드
def solution(numbers):
    from itertools import permutations
    maxfind = list(permutations(numbers,len(numbers)))

    for i in range(len(maxfind)):
        maxfind[i] = int(''.join(list(map(str,maxfind[i]))))
    return str(max(maxfind))

하지만 위의 코드는 아무래도 모든 숫자의 permutation들을 구해서 또 문자열로 바꾸는 방법을 사용하다 보니 시간 초과가 나왔다.

 

 

3. 시간 초과 해결

def solution(numbers):

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

 

아직 lambda에 익숙하지가 않아서 다른 사람들 코드 보면서 사용 방법을 알아갔다. 

 

 

위 코드 분석 

 

1) i * 3 

i * 3 -> numbers가 0부터 1000이하의 정수이기 때문

 

ex) [30, 3, 9, 332]가 주어졌을 경우 

만약 i * 2를 했더라면 3030, 33, 99, 332332를 비교하게 되는데  문자열 정렬 했을 때 332보다 33이 앞에 나오기 때문에  i * 3을 하여 303030, 333, 999, 332332332를 비교하여 333을 332보다 앞에 정렬한다. 

 

2) reverse = True

303030, 332332332, 333, 999의 정렬을 뒤집어서 하기 위함

 

3) str(int(''.join(numbers)))

[0,0,0,0] 인 경우 처리하기 위함 

0000이 아닌 0으로 출력하기 위해서 

 

 

 

 

 

 

---

문제 출처

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