학습 주제
코딩테스트 연습
정렬 - 가장 큰 수

학습 내용

숫자, 문자열이 아닌 우리가 정하는 순서에 따라 정렬할 수 있는가?

지난번에 엄청 시행착오 겪으면서 풀었던 문제이다. 그때는 패딩으로 해결.

10보단 2가 앞에 나오는게 큰 수를 만드는데 유리함

-제한사항
- 1<=numbers<=100000
- numbers원소는 최대 4글자

문제의 해결 방법

예제에 적용

• 처음 빈 문자열로 초기
• 목록 중 9가 가장 크므로 문자열 옮김
• 그다음 5를 고름
• 34를 고름
• 과정을 반복하면 3과 30 중 3이 먼저 와야함. 이게 문제임.
  
• 임의의 조건 '30' 과 '3' 중 '3'을 선택해야함.
• n^2 의 복잡도가 걸리는 알고리즘

(조금 나은) 문제의 해결방법

• 빈 문자열로 수 초기화
• 수의 목록 (결과를 크게 만드는 것 우선으로) 정렬한다.
• 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
• 모든 수를 다 야용할 때까지 반복한다.
  nlogn 복잡도
  두번째를 어떻게 정렬할 것인가.

정렬에 사용되는 기준을 문자열로 취급했을 때 앞에 세웠을 때 결과적으로 큼

• 수가 길이가 같으면 큰게 우선하는 것이 맞음.
  
  
  
• 앞자리가 같고 서로 다른 길이일 때. 조금 더 비교해본다.
  
  
  

알고리즘 설계 -> 구현