백준 - 버블 소트 1517번
👏 key point
* 데이터 입력과 그에 따른 시간복잡도
-
O(N^3)$ 알고리즘: 크기 2560인 입력까지를 1초 안에 풀 수 있습니다. 이때 은 대략 16억입니다.
-
O(N^2)$ 알고리즘: 크기 40960인 입력까지를 1초 안에 풀 수 있습니다. 이때 은 대략 16억입니다.
-
O(N \lg N)$ 알고리즘: 크기가 대략 2천만인 입력까지를 1초 안에 풀 수 있습니다. 이때 은 대략 5억입니다.
-
O(N)$ 알고리즘: 크기가 대략 1억 6천만인 입력까지를 1초 안에 풀 수 있습니다.
따라서 버블 소트는 단순하게 이중 포문으로 일일이 하나씩 비교를 한다면 쉽게 풀 수 있지만 시간복잡도 문제로 불가능 하다. 따라서 우리는 nlogn 의 시간복잡도로 풀 수 있는 병합정렬을 이용해 버블 소트를 풀려고 할 것이다.
[1256][3478]
이렇게 병합 정렬에 의해 분해된 두 리스트가 있다고 하자 이 두 리스트를 병합하기 위해서 두 리스트의 목록을 비교하는데 만약 오른쪽에 있는 리스트 값이 새로운 리스트에 들어온다고 한다면 cnt += 1을 해준다. (바꿔줘야 하므로) 그리고 왼쪽에 있는 리스트가 새로운 리스트에 들어온다면 result += cnt를 해준다.
따라서 하나의 숫자 당 swap 해줘야 하는 개수를 cnt라고 보면 된다.
예를 들어
12가 들어오고 (이때, 자리 변화가 없으므로 cnt = 0, result = 0)
[1,2]
3과 4 가 5,6 보다 작으니까 34가 들어 온다.
[3,4]
(이때, 5,6이 원래 자리 보다 밀려 났으므로 cnt = 2, result = 0)
다시 5,6이 들어오려고 할 때는 원래 자리 보다 2만큼 밀려났으므로(cnt = 2)
그만큼 더 해줘야한다. (result += cnt)
[1,2,3,4,5,6]
뒤에 있는 7,8은 swap을 하지 않는다.
답 : 4
🎂 코드
n = int(input())
lst = list(map(int, input().split()))
result = 0
def srt(lst):
global result
#lst의 길이가 1이 될 때까지 분할
if len(lst) <= 1:
return lst
#분할
a = srt(lst[:len(lst) // 2])
b = srt(lst[len(lst) // 2:])
#병합
i = 0
j = 0
cnt = 0
#매 순간마다 정렬하기 위해 리셋
merg = []
while i < len(a) and j < len(b):
#왼쪽 리스트의 값이 들어올 때
if a[i] <= b[j]:
merg.append(a[i])
i += 1
result += cnt
#오른쪽 리스트의 값이 들어올 때
else:
merg.append(b[j])
j += 1
cnt += 1
#두 리스트 중 한 리스트의 값이 모두 소진 되었을 때
while i < len(a):
merg.append(a[i])
result += cnt
i += 1
while j < len(b):
merg.append(b[j])
j += 1
return merg
srt(lst)
print(result)
Author And Source
이 문제에 관하여(백준 - 버블 소트 1517번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@turtle601/백준-버블-소트-1517번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)