정렬(sort) : 가장 큰 수

정화·2024년 3월 29일

TIL

목록 보기
5/11

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

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

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

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

문제 해결 방법
1. 빈 문자열로 수를 초기화한다.
2. 가장 크게 만들 수 있는 수를 고른다
3. 그 수를 현재 수에 이어붙인다
4. 모든 수를 다 사용할 때까지 반복


이건 각 단계마다 목록의 길이에 비례..
O(n^2)의 복잡도를 가짐.

그떄 sort이용
1. 빈 문자열로 수를 초기화한다.
2. 수의 목록을 앞자리가 큰 숫자를 우선으로 해서 정렬한다
3. 그리고 그걸 이어붙인다
4. 모든 수를 다 사용할 때까지 반복
nlogn의 복잡도를 가지므로 훨씬 효율성이 높다!
but 오름차순 내림차순 순서가 아니므로 그것을 조심하자!

크게 만드는 수의 기준
1

profile
개발자를 꿈꾸는..

0개의 댓글