정렬 - 몸풀기 문제

### 문제 54 계수 정렬 구현하기

인자로 받은 문자열 s를 계수정렬로 정렬하여 반환하는 함수 구현

계수정렬은 문자를 정렬할 때 매우 효율적인 알고리즘

def solution():
	counts=[0]*26
    
    for c in s:
    	counts[ord(c)-ord("a")]+=1
    	
    sorted_str=""
    for i in range(26):
    	sorted_str+=chr(i+ord("a"))*counts[i]
    return sorted_str    
   	

a의 아스키코드 값은 97이므로, 그대로 빈도수 배열에 저장하려면 97번째부터 빈도 수를 저장해야함
a를 일괄로 빼면 인덱스 0부터 빈도수를 저장할 수 있음 !

### 문제 55 정렬이 완료된 두 배열 합치기

이미 정렬이 완료되어 있는 두 배열 arr1, arr2을 받아 병합 정렬하는 함수 구현

def solution(arr1,arr2):
	merged=[]
    i,j=0,0
    while i<len(arr1) and j<len(arr2):
    	if arr1[i]<arr2[j]:
        	merged.append(arr1[i])
            i+=1
        else:
        	merged.append(arr2[i])
            j+=1
            
    while i<len(arr1):
    	merged.append(arr1[i])
        i+=1
    while j<len(arr2):
    	merged.append(arr2[i])
        j+=1
    return merged

-> O(N+M) arr1의 원소의 개수 N, arr2의 원소의 개수 M 이라고 하면 배열을 합치면서 모든 원소를 한번씩 순회하므로