백준-24060문제 풀이

[백준 병합정렬 문제]
https://www.acmicpc.net/problem/24060

이번에 푼 문제는 병합정렬에 관한 문제였다
병합정렬의 개념은 알았지만 실제로 구현은 처음 해보는 거여서
여기 적어보려고 한다

병합정렬이란

하나의 리스트를 균등하게 분할하고 부분 리스트를 정렬한 뒤 다시
합쳐서 오름차순이나 내림차순으로 순서를 조립하는 방법이다!

계속 분할한 뒤 각각의 수 하나씩을 다시 비교하면서 합치는 방식이다!

내가 작성한 코드

코드를 작성할 때 두가지가 필요했다

1. 재귀함수로 어떻게 계속 분할할지
2. 다시 합칠때 어떻게 합칠지

import sys
input = sys.stdin.readline

def merge(L):
	if len(L) == 1:
    	return L
    mid = len(L) // 2 +1 # 중간부분을 구해서 나눠줘야해서 필요하다!
    left = merge(L[:mid]) #왼쪽부분 나눈거
    right = merge(L[mid:]) # 오른쪽 부분 나눈거
    
    i,j = 0,0
    L2 = [] # 위에서도 if에서 return 했기 때문에 return 할 []이 필요하다
    
    # 이 부분이 각각의 왼쪽 오른쪽을 비교하는 부분이다 
    # 비교 후 남는 곳은 나중에 추가로 넣어준다
    while i < len(left) and j < len(right): 
    	if left[i] < right[j]:
        	L2.append(left[i])
            ans.append(left[i])
            i +=1
        else:
        	L2.append(right[j])
            ans.append(right[j])
            j+=1
     if len(left) == i: #즉 오른쪽 리스트가 남았을경우 남은 부분을 다 넣어준다
     	while j<len(right):
        	L2.append(right[j])
            ans.append(right[j])
            j+=1
     else: 
     	while i<len(left):
     		L2.append(left[i])
            ans.append(left[i])
            i +=1
     
     return L2

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
merge(a)

if k <= len(ans):
	print(ans[k-1])
else:
	print(-1)

피드백

병합 정렬 부분은 나중에 요긴하게 쓰일수도 있으니까 한번씩 보면서 잊지말자