03 가장 큰 수 - 풀이

문제 설명

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

예를 들어, 주어진 정수가 [6, 10, 2] 라면, [6102, 6210, 1062, 2610, 2106]을 만들 수 있고, 이중 가장 큰 수는 6210 입니다.

0또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요

 

제한 사항

numbers의 길이는 1이상 100,000 이하 입니다.

numbers의 원소는 0이상 1,000 이하 입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

[3, 30, 34, 5, 9] -> '9534330'

---

풀이

- 정렬 문제

1. 빈 문자열로 수를 초기화

2. 가장 크게 만들 수 있는 수를 고른다

3. 그 수를 현재 수에 이어 붙인다.

4. 모든 수를 다 사용할 때까지 반복

[3, 30, 34, 5, 9]	""
[3, 30, 34, 5]	"9"
[3, 30, 34]	"95"
[3, 30]	"9534"
[30]	"95343"
[]	"9534330"

1. 빈 문자열로 수를 초기화

2. 수의 목록(크게 만드는 것 우선으로)을 정렬 - 내림차순 : 기준 - 정수의 대소관계 X

3. 목록에서 하나씩 꺼내어 현재수에 이어 붙인다.

4. 모든 수를 다 사용할 때까지 반복한다.

 

"크게 만드는 수의 기준"의 성립이 중요

3 VS 32 -> 332, 323 - 3 우선

3 VS 33 -> 아무거나

3 VS 34 -? 334 , 343 - 34 우선

- 길이가 다른 수의 비교 : 주어진 수는 1000이하 이기 때문에 4글자로 끊어서 비교

34  - 3434/343 ...

343 - 3433/43343 ...

---

내 코드

def solution(numbers):  # numbers : 0또는 양의 정수가 담긴 배열
    answer = ''         # 정수를 이어 붙여 만들 수 있는 가장 큰수
    
    numbers = list(map(str, numbers))   # int -> 문자형으로 변환
    numbers.sort(reverse=True)          # 내림차순으로 정렬

    # 첫번째 숫자가 가장 큰거 부터    
    answer = ''.join(numbers)

    return answer

- 머릿속으로는 풀이방법을 떠올렸으나 풀지는 못해서 결국 검색 찬스 했다가 복붙으로 제출하긴 좀 그래서, 내가 아는 수준에서 해결해보려고 했지만 풀지 못했다 ㅜ

 

✅문제점

1. 앞의 있는 수가 큰 수가 크게 만드는 수일 것이라는 대소관계 비교를 위한 기준은 떠올렸으나, 정렬을 하지 못했음

2. 파이썬 문법 잘 모름 lambda

 

---

풀이

def solution(numbers):
	numbers = [str(x) for x in numbers]		# 문자열로 취급하기 위해 문자열로 변환
    
    # 문자열 4번 반복, 4글자로 slice한걸로 내림차순 정렬
    numbers.sort(key=lambda x : (x * 4)[:4], reverse=True)	
	answer = ''.join(numbers)	# 문자열 연결
    
    return answer

- 마지막 정확도 테스트 실패 > number는 0이상 1,000 이하이기 때문, 0000리턴 하면 안됨

def solution(numbers):
	numbers = [str(x) for x in numbers]		# 문자열로 취급하기 위해 문자열로 변환
    
    # 문자열 4번 반복, 4글자로 slice한걸로 내림차순 정렬
    numbers.sort(key=lambda x : (x * 4)[:4], reverse=True)	
    
    if numbers[0] == '0':
    	answer = '0'
    else:
    	answer = ''.join(numbers)	# 문자열 연결
    
    return answer

💯 > 0에 대한 처리하여 통과

- 복잡도 : 정렬이 지배적, O(nlogn)

 

 

쉬운 문젠데도 풀지 못한다니 ,,, 반성하고 더 열심히 공부하도록 하자