021 버블 소트

첫번째 코드

 

버블 소트 문제인 만큼, 버블 소트를 이용하여 정렬하면서 swap을 한 경우 1씩 결과에 저장해주는 코드를 작성한다.

 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
swap_count = 0

for i in range(n-1):
    for j in range(n-i-1):
        if A[j] > A[j+1]:
            tmp = A[j]
            A[j] = A[j+1]
            A[j+1] = tmp
            swap_count += 1

print(swap_count)

 

맞는 듯 하나 시간초과가 나타난다...

---

두번째 코드

 

책을 참고하여 진행한 결과 이 문제는 병합 정렬을 이용하여 푸는 것이다!

이때 코드는 이전 문제와 거의 동일하나 중간에 swap한 경우 해당 개수를 더해주는 것이 추가되었다.

 

import sys
input = sys.stdin.readline

result = 0

def merge_sort(s, e):
    global result
    if e - s < 1:
        return
    m = int(s + (e - s) / 2)
    merge_sort(s, m)
    merge_sort(m + 1, e)
    
    
    for i in range(s, e + 1):
        tmp[i] = a[i]
    
    k = s
    index1 = s
    index2 = m + 1

    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]:
            a[k] = tmp[index2]
            result = result + index2 - k
            k += 1
            index2 += 1
        else:
            a[k] = tmp[index1]
            k += 1
            index1 += 1

    while index1 <= m:
        a[k] = tmp[index1]
        k += 1
        index1 += 1
    while index2 <= e:
        a[k] = tmp[index2]
        k += 1
        index2 += 1
    
n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
tmp = [0] * int(n + 1)

merge_sort(1, n)

print(result)

 

통과!

 

병합 정렬 자체를 혼자서 푸는 코드를 여러번 작성해보아야 할 것 같다...으어 어렵다 ㅠㅠ

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/1517.%E2%80%85%EB%B2%84%EB%B8%94%E2%80%85%EC%86%8C%ED%8A%B8

programmers/백준/Platinum/1517. 버블 소트 at main · ornni/programmers