[백준 - python] 24060번: 알고리즘 수업 - 병합 정렬 1

<문제 링크>

24060번: 알고리즘 수업 - 병합 정렬 1

 

<문제 풀이>

def merge_sort(A, p, r): # A[p ~ r]을 오름차순 정렬한다.
  if p < r:
    q = (p + r) // 2; # q는 p, r의 중간 지점
    merge_sort(A, p, q)       # 전반부 정렬
    merge_sort(A, q + 1, r)   # 후반부 정렬
    merge(A, p, q, r)         # 병합

# A[p~q]와 A[(q+1)~r]을 병합하여 A[p~r]을 오름차순 정렬된 상태로 만든다.
# A[p~q]와 A[(q+1)~r]은 이미 오름차순으로 정렬되어 있다.
def merge(A, p, q, r):
  global cnt, res
  i = p
  j = q + 1
  tmp = []
  
  while i <= q and j <= r:
    if A[i] <= A[j]:
      tmp.append(A[i])
      i += 1
    else:
      tmp.append(A[j])
      j += 1
    
  while i <= q: # 왼쪽 배열 부분이 남은 경우
    tmp.append(A[i])
    i += 1
  
  while j <= r: # 오른쪽 배열 부분이 남은 경우
    tmp.append(A[j])
    j += 1
  
  i = p
  t = 0
  
  while i <= r:  # 결과를 A[p~r]에 저장
    A[i] = tmp[t]
    cnt += 1
    if cnt == K:
       res = A[i]
       break;
    i += 1
    t += 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
res = -1
merge_sort(A, 0, N - 1)
print(res)

24060 입출력 예시

*key point: 주어진 크기가 N인 배열에 대한 병합 정렬 의사 코드를 파이썬으로 구현해 준다. merge 함수 실행 과정에서 결과를 저장하는 부분에서 횟수를 세어주는 알고리즘을 추가하여 활용한다.

 

*위의 예시에서 저장이 발생할 때마다 출력을 수행한 결과는 다음과 같다.