[백준] 24060번 : 알고리즘 수업 - 병합 정렬 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

2. 풀이과정

해당 문제는 배열의 원소들을 오름차순으로 정렬하며 각 과정별로 저장되는 값을 저장하고 이를 횟수에 따라 출력하는 문제이다.

문제에 나와있는 배열을 병합 정렬하는 코드를 활용해 정렬을 수행하는데, 여기서 각 과정별로 저장되는 값을 따로 저장해줘야 하므로 해당 값을 저장할 리스트를 생성해 과정별로 저장되는 값을 해당 리스트에 추가한다.

만약 저장된 값의 개수가 입력으로 받은 저장 횟수보다 작으면 해당 순서의 값을 구할 수 없으므로 -1을 반환하고, 저장된 값의 개수가 입력으로 받은 저장 횟수보다 크거나 같으면 해당 순서의 값을 출력한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 정렬할 배열의 시작과 끝 위치를 인수로 하는 함수 merge_sort를 정의한다. def merge_sort(s, e)
3. 만약 시작 위치가 끝 위치보다 작으면 if (s < e)
4. 중간 지점을 구한다. m = (s + e) // 2
5. 그리고 중간 지점을 기준으로 배열을 앞부분과 merge_sort(s, m)
6. 뒷부분으로 분리한다. merge_sort(m + 1, e)
7. 각 앞부분과 뒷부분을 정렬했으면 두 배열을 병합한다. merge(s, m, e)
8. 정렬된 두 배열을 병합하는 함수 merge를 정의한다. def merge(s, m, e)
9. 앞부분 배열의 시작 위치를 새로운 변수에 저장한다. i = s
10. 뒷부분 배열의 시작 위치를 새로운 변수에 저장한다. j = m + 1
11. 정렬할 위치를 시작 위치로 저장한다. t = s
12. 앞부분 배열의 시작 위치가 끝 위치인 중간 지점이 되기 전까지, 그리고 뒷부분 배열의 시작 위치가 끝 위치인 배열의 끝 위치가 되기 전까지 반복한다. while (i <= m and j <= e)
13. 만약 전체 배열의 앞부분 배열 위치 값이 뒷부분 배열 위치 값보다 작거나 같으면 if (A[i] <= A[j])
14. 작은 값을 앞으로 정렬해야 하므로 해당 값을 저장되는 값 리스트에 추가한다. result.append(A[i])
15. 임의의 배열의 정렬할 위치에 해당 값을 저장한다. tmp[t] = A[i]
16. 제일 작은 값을 정렬했으므로 정렬할 위치를 증가시킨다. t += 1
17. 앞부분 배열의 원소를 정렬했으므로 다음 원소를 가리킨다. i += 1
18. 반면에 전체 배열의 앞부분 배열 위치 값이 뒷부분 배열 위치 값보다 크면 else
19. 작은 값을 앞으로 정렬해야 하므로 해당 값을 저장되는 값 리스트에 추가한다. result.append(A[j])
20. 임의의 배열의 정렬할 위치에 해당 값을 저장한다. tmp[t] = A[j]
21. 제일 작은 값을 정렬했으므로 정렬할 위치를 증가시킨다. t += 1
22. 뒷부분 배열의 원소를 정렬했으므로 다음 원소를 가리킨다. j += 1
23. 두 배열을 비교해 정렬한 후, 만약 앞부분 배열의 원소가 남았다면 while (i <= m)
24. 남은 값들을 하나씩 가져와 저장되는 값 리스트에 추가하고 result.append(A[i])
25. 임의의 배열에도 저장하고 tmp[t] = A[i]
26. 제일 작은 값을 정렬했으므로 정렬할 위치를 증가시킨다. t += 1
27. 앞부분 배열의 원소를 정렬했으므로 다음 원소를 가리킨다. i += 1
28. 두 배열을 비교해 정렬한 후, 만약 뒷부분 배열의 원소가 남았다면 while (j <= e)
29. 남은 값들을 하나씩 가져와 저장되는 값 리스트에 추가하고 result.append(A[j])
30. 임의의 배열의 정렬할 위치에 해당 값을 저장한다. tmp[t] = A[j]
31. 제일 작은 값을 정렬했으므로 정렬할 위치를 증가시킨다.  t += 1
32. 뒷부분 배열의 원소를 정렬했으므로 다음 원소를 가리킨다. j += 1
33. 임의의 배열에 병합한 결과를 원래 배열에 저장하기 위해 원래 배열의 시작 위치를 지정하고 i = s
34. 임의의 배열의 시작 위치를 지정한다. t = s
35. 원래 배열의 시작 위치가 끝 위치가 될 때까지 반복하며 while (i <= e)
36. 임의의 배열의 값을 원래 배열에 저장한다. A[i] = tmp[t]
37. 두 위치 모두 다음 위치로 이동한다. i += 1  t += 1
38. 두 함수를 모두 정의했다면 배열의 크기와 저장 횟수를 입력받는다. N, K = map(int, sys.stdin.readline().split())
39. 배열의 원소를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
40. 임의의 배열을 원래 배열의 크기로 생성한다. tmp = list(0 for _ in range(N))
41. 저장되는 수를 저장할 리스트를 생성한다. result = list()
42. 해당 배열의 시작 위치와 끝 위치를 인수로 하여 merge_sort 함수를 실행시킨다. merge_sort(0, N - 1)
43. 배열이 정렬된 후, 저장되는 수에 저장된 원소 개수가 입력받은 저장 횟수보다 크거나 같으면 if (K <= len(result))
44. 저장 횟수에 저장한 값을 출력한다. print(result[K - 1])
45. 반면에 저장되는 수에 저장된 원소 개수가 입력받은 저장 횟수보다 작으면 else
46. -1을 출력한다. print(-1)

반응형

3. 소스코드

import sys

def merge_sort(s, e):
    if (s < e):
        m = (s + e) // 2
        merge_sort(s, m)
        merge_sort(m + 1, e)
        merge(s, m, e)

def merge(s, m, e):
    i = s
    j = m + 1 
    t = s
    
    while (i <= m and j <= e):
        if (A[i] <= A[j]):
            result.append(A[i])
            tmp[t] = A[i]
            t += 1
            i += 1
        else:
            result.append(A[j])
            tmp[t] = A[j]
            t += 1
            j += 1

    while (i <= m):
        result.append(A[i])
        tmp[t] = A[i]
        t += 1
        i += 1
    while (j <= e):
        result.append(A[j])
        tmp[t] = A[j]
        t += 1
        j += 1

    i = s
    t = s
    while (i <= e):
        A[i] = tmp[t]
        i += 1
        t += 1
        
N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

tmp = list(0 for _ in range(N))
result = list()
merge_sort(0, N - 1)

if (K <= len(result)):
    print(result[K - 1])
else:
    print(-1)