[코테스터디 day3] 정렬

✏️ 정렬

in python

• list1.sort()
  • 시간 복잡도 O(nlogn)에 근접 -> 최적화 잘되어있다고 함 (quicksort -> O(nlogn)) 
  • sort 옵션
    • sort(key=len) -> 정렬 기준을 지정하는 함수나 함수를 반환하는 식을 제공 (len 함수 등)
    • sort(reverse = True) -> 내림차순 정렬 (기본값 : 오름차순)
• list1 = sorted(list2)

 

Lambda식

• 기본 형식
  • lambda 인자: 반환값
  • lambda x:x[1] -> x 인자에서 index 1의 원소를 반환
• lambda와 sort의 조합
  • sort(key=lambda x:x[0]) 

 

 

✏️  오늘의 문제 : 가장 큰 수

 

 

 

 

📌 주안점

• 정렬의 기준을 잡는 문제 -> python의 key=lambda, java의 Comparator을 잘 구현하는 문제
• 숫자로 가장 큰 수를 비교정렬하는 것보다, 문자로 비교하는 방식이 더 용이함
• 문자열 비교 기준 (사전순)
  • "7" < "8"
  • "8" < "88"
  • "8" < "89"
  • "10" < "2"
  • 숫자가 작을수록, 길이가 짧을수록 더 앞
• 1000을 제외한 모든 문자는(1~999) *3을 하고 앞 세자리만 비교한다면, 요구사항과 완벽히 부합
  • 1~9는 111,222,..,999로
  • 10~99는 101(010), 121(212), 565(656) 으로 가장 앞선 위치의 문자가 맨 뒤의 문자와 일치하므로, 앞 세자리를 비교해서 큰 수를 찾는 요구사항에 적합 
  • 100~999는 같은 문자 *3 이므로, 앞 세자리만 비교할 때 동일

📌 풀이

• 숫자로 계속 시도하다 답을 찾아봤다.

 

 

 

 

✏️  추가 문제1 : K번째 수

 

풀이

• 그냥 슬라이싱하고 정렬