문제
0 또는 양의 정수가 주어졌을 때 정수를 이어 붙여 만들 수 있는 가장 큰수를 문자열로 바꾸어 return해라
0또는 양의 정수가 담긴 배열 numbers가 매개변수
ex) 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]만들 수 있고, 이 중 가장 큰 수 6210
<제한>
numbers의 길이는 1이상 100,000이하
numbers의 원소는 0이상 1,000이하
정답 너무 클 수 있으니 문자열로 바꿔 return
어떻게 해결할까
1.
빈 문자열로 수 초기화
2.
가장 크게 만들 수 있는 수 고름
3.
그 수를 현재 수에 이어 붙임
4.
모든 수를 다 사용할 때 까지 반복
위의 예로 살펴본다면 6 + 2 + 10이렇게
<복잡도?>
요소를 살펴보는 단계가 주어진 배열의 길이에 비례하고 단계별로 또 요소를 다 살펴봄
따라서 배열의 길이가 N이라고 했을 때
의 복잡도를 갖게됨
정렬을 통해 조금 더 개선해보기
1.
빈 문자열로 수를 초기화
2.
수의 목록을 크게 만드는 것 우선으로 정렬
3.
목록에서 하나씩 꺼내 현재 수에 이어 붙임
4.
모든 수를 다 사용할 때까지 반복
"크게 만든다"의 기준은
3 vs 32 → 332 vs 323 → 3을 먼저놔야함
3 vs 33 → 333 vs 333 → 아무거나 먼저 써도 됨. 우선순위 동일
3 vs 34 → 334 vs 343 → 34를 먼저 써야함
34 vs 343 → 34343 vs 34334 → 34를 먼저 써야함
이 기준으로 정렬하여 먼저 뽑아주면 된다
⇒
34보다 뒤에 있을 수 있는 수는 34를 넘지 못한다. 뒤에 올 수 있는 가장 큰수: 343434....
343뒤에 있을 수 있는 수 또한 343을 넘지못한다. 뒤에 올 수 있는 가장 큰수 : 343343343...
⇒ numbers의 원소는 0이상 1000이하이므로 세자리를 잘라주면 343
알고리즘 구현
정렬의 복잡도 :
•
대소 관계를 비교하기 위한 기준을 마련해야 하고
•
이것을 이용해 주어진 배열을 정렬해야 하고
•
정렬된 배열을 이용해 문자열 표현을 완성해야 한다.
def solution(numbers):
numbers = list(map(str, numbers)) # 문자열로 형변환
# 정렬 key 설정을 lambda function을 활용
# x라는 원소가 주어지면 (여기선 문자열) 문자열을 3번 반복, 내림차순 정렬을 위해 reverse=True
numbers.sort(key=lambda x: (x*3), reverse=True)
if numbers[0] == '0': # 첫번째 원소가 0이면 뒤에 원소도 모두 0이라는 말이므로 이 때는 000000.... 이 아닌 '0'을 반환해줘야 한다.
return '0'
else:
return ''.join(numbers) # join 메소드를 통해 모든 원소를 이어붙여준 뒤 반환
Python
복사
[복잡도]
문자열로 형변환하는 첫번째 부분 :
이 코드의 복잡도를 지배하는 부분은 정렬하는 부분이다 :
