[분할정복] 백준 1517 - 파이썬

 

의식의 흐름 알고리즘은 문제를 보고 내가 첨에 든 생각들을 끄적인거라 틀린 알고리즘임.

답만 알고 싶다면 최종 알고리즘이나 정답코드만 보면 된다.

 

백준 1517.

https://www.acmicpc.net/problem/1517

 

---

의식의 흐름 알고리즘

버블소트가 뭔지는 아마 알것이라고 생각한다..

처음부터 인접해있는 친구들을 비교해가며 front > back이면 두개의 순서를 바꾸며 끝까지가고

다시 앞에서부터 반복하는데 끝까지 - 1 만큼만 가는 형식이다.

 

틀린답 - 시간초과

def bubble():
    n = int(input())
    arr = list(map(int, sys.stdin.readline().split()))
    
    cnt = 0
    for val in range(n-1, 0,-1):
        for i in range(val):
            if arr[i]>arr[i+1] :
                f = arr[i]
                b = arr[i+1]
                arr[i+1] = f
                arr[i] = b
                cnt +=1
    print(cnt)

 

뭐지 그냥 순수하게 구현하면 되는거 아니었나ㅋㅋㅋㅋㅋㅋ 버블소트는 원래 시간복잡도 구데기인뎅...

너무 단순히 생각했나보다.

 

 

 

최종 알고리즘

찾아보니 나같은 사람이 많네. 위안이 된다. 암튼 이건 병합정렬로 풀어야한다.

애초에 1초 있고 범위 엄청 많은거 보면서 버블소트로 이게 되나..? 생각은 했지만.. 그럴거면 제목을 저렇게 하지말지!!!!!!!

 

 

우선 병합정렬에 대해 먼저 알아보고 가자

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

 

그리고 문제 적용은

def bubble():
    n = int(input())
    cnt = 0
    arr = list(map(int, input().split()))

    def merge(left, right):
        nonlocal cnt
        i, j = 0, 0
        temp = []
        while i < len(left) and j < len(right):

            if left[i] > right[j]:
                temp.append(right[j])
                j += 1
                cnt += len(left) - i  # 왼쪽과 오른쪽을 비교했을 때 만약 오른쪽이 왼쪽보다 작다면,
                # 왼쪽의 남은 확인하지않은 인덱스들은 오른쪽보다는 당연히 큰 값으로 남아있으므로
                # 그 수만큼 갯수를 더해주면 됩니다.
            else:
                temp.append(left[i])
                i += 1

        if i == len(left):
            temp.extend(right[j:])
        else:
            temp.extend(left[i:])
        return temp


    def merge_sort(list):
        if len(list) <= 1:
            return list
        else:
            mid = len(list) // 2
            left = merge_sort(list[: mid])
            right = merge_sort(list[mid:])
            return merge(left, right)



    arr = merge_sort(arr)
    print(arr)
    print(cnt)