문제 2122

합병정렬

시간 제한 1.000초 메모리 제한 128MB

제출

바로가기

문제 설명

합병정렬이란 자료를 반으로 나누고 각 부분을 정렬한 후 병합하는 방식이다. 이 과정을 재귀적으로 반복하여 효율적으로 대규모 데이터를 정렬할 수 있다.

<img src="/upload/judge.codingpanda.kr/image/20250121/20250121153655_16805.gif" alt="Swfung8, CC BY-SA 3.0 , via Wikimedia Commons” />

다음과 같이 합병정렬 알고리즘 코드가 주어졌을 때 빈 영역에 들어갈 코드를 작성하시오.

#미리 작성된 코드
n=int(input())
A=list(map(int, input().split()))
B=[0]*len(A)
f(0,len(A)-1)
print(*A)
##미리 작성된 코드는 제출 코드 뒤에 붙습니다.

입력 설명

데이터의 수 n이 입력된다.
n개의 데이터가 공백으로 구분되어 입력된다.

출력 설명

정렬된 데이터가 출력된다.

입력 예시

5
9 3 2 8 1

출력 예시

1 2 3 8 9

제출 코드 가이드

앞부분 제공 코드

제출자가 작성할 코드 영역

def f(low, high):
  if low>=high:
    return
  mid = {{여기에 들어갈 코드를 입력하세요.}}
  f({{여기에 들어갈 코드를 입력하세요.}})
  f({{여기에 들어갈 코드를 입력하세요.}})
  i = low
  j=mid+1
  for k in range(low, high+1):
    if j>high:
      {{여기에 들어갈 코드를 입력하세요.}}
      {{여기에 들어갈 코드를 입력하세요.}}
    elif i>mid:
      {{여기에 들어갈 코드를 입력하세요.}}
      {{여기에 들어갈 코드를 입력하세요.}}
    elif A[i]<=A[j]:
      {{여기에 들어갈 코드를 입력하세요.}}
     {{여기에 들어갈 코드를 입력하세요.}}
    else:
      {{여기에 들어갈 코드를 입력하세요.}}
      {{여기에 들어갈 코드를 입력하세요.}}
    k=k+1
  for k in range(low,high+1):
    A[k]=B[k]
  return

뒷부분 제공 코드

#

n=int(input())
A=list(map(int, input().split()))
B=[0]*len(A)
f(0,len(A)-1)
print(*A)

출처

정보과학