정렬

<프로그래머스 고득점kit>

<K번째수>

def solution(array, commands):
    answer = []
    for [a,b,c] in commands:
        sub_array=array[a-1:b]	#i부터 j까지 자른다.
        sub_array.sort()	#n번째 큰수를 바로추출하기위해 정렬
        answer.append(sub_array[c-1])
    return answer

<해설>

인자로 주어진 배열의 길이가 작기때문에 sort()메서드를 통해 시간복잡도를 충분히 통과할 수 있다.

<가장 큰 수>

def comp(a,b):	#a와 b는 각각 정수로 들어옴 
  a=str(a)	#20이 들어오면 '20'의 문자열로 변환
  b=str(b)	
  if(int(a+b)>int(b+a)):	#알뒤로 붙였을때 더 큰 결과물 추출   ex)a-'22' b-'23'이면 '2223','2322'중 큰것을 추출
    return 0		#0이면 왼쪽 것을 먼저 집어넣어라
  else:				
    return 1		#1이면 오른쪽 것을 먼저 집어넣어라
#		
def merge_sort(arr):
    if len(arr) < 2:
        return arr
#
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
#
    merged_arr = []
    l = r = 0
    while l < len(left_arr) and r < len(right_arr):
        if comp(left_arr[l],right_arr[r]) == 0:
            merged_arr.append(left_arr[l])
            l += 1
        else:
            merged_arr.append(right_arr[r])
            r += 1
    merged_arr += left_arr[l:]
    merged_arr += right_arr[r:]
    return merged_arr
def solution(numbers):
    result = merge_sort(numbers)
    result=''.join(str(_) for _ in result)
    if(int(result)==0):
        return '0'
    return result

<해설>

시간복잡도로 인해 최대 n*log(n)을 가지는 병합정렬로 순회를 하며 앞,뒤문자를 서로 순서를 다르게 붙였을 때 더 큰 것을 기준으로 정렬한다.

<예외케이스>만약 [0,0,0,0,0]처럼 모든 원소가 0인 경우에는 return처리가 '00000'이므로 따로 조건을 걸어 처리

< H-index >

def merge_sort(arr):	#병합정렬
    if len(arr) < 2:
        return arr
#
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
#
    merged_arr = []
    l = r = 0
    while l < len(left_arr) and r < len(right_arr):
        if (left_arr[l]<right_arr[r]):
            merged_arr.append(left_arr[l])
            l += 1
        else:
            merged_arr.append(right_arr[r])
            r += 1
    merged_arr += left_arr[l:]
    merged_arr += right_arr[r:]
    return merged_arr
def solution(citations):
    merged=merge_sort(citations)
    h_index=0
    for v in range(1,len(merged)+1):	#h-index는 배열의 길이보다 클 수가 없다!
      if(merged[len(merged)-v]>=v):		#h-index를 차근히 늘려가는데 len(merged)-v인덱스로 갔는데 그 값이 v보다 크다면 무조건 v개 이상 존재하는 것이므로 h-index를 최신화!
        h_index=v
      else:
        break
    return h_index

<해설>

병합정렬을 통해 nlog(n)으로 정렬 후 최대 h-index는 배열의 길이이므로 n번 반복을 하면 결국 nlog(n)의 복잡도가 나오고 1서부터 늘려가며 자신이 최소길이에 인덱스를 주었을 때 크기가 크다면 그만큼 가지고 있는 것이므로 통과하면서 h-index의 최대크기를 탐색한다.