[백준] 1517 버블 소트, python

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

 

 

 

 

버블 소트로 정렬을 할 때, 수의 교체가 몇 번 일어나는지를 세는 문제이다.

n*n의 모든 경우를 탐색하며 개수를 세어주면 시간초과가 난다.

작은 값이 앞쪽에 와야하므로, 배열에서 현재 선택된 수의 오른쪽 부분에서 현재 수보다 작은 값이라면 교체를 해주어야 한다.

예를 들어 배열이 [3,4,2,1]이라 하면,

 

 

먼저 배열의 요소를 크기순으로 정렬하여 작은 것부터 순서대로 0,1,2.. 에 매핑시켰다.

 

이렇게 되면 처음 배열 [2,3,1,0]에서 2는 1과 0, 3은 1과0, 1은 0과 교체해야 한다.

 

 

즉 배열에서 i번쨰 값을 k라 하면, i+1부터 배열의 끝까지 k보다 작은 요소의 개수를 세어주면 된다.

 

 

 

[백준] 7578 공장

[백준] 7578 공장

 

7578 공장 문제는 현재 배열에서 i번째 값이 k일 때 0~i-1에서 k보다 큰 것의 개수를 세는 문제이다.

 

 

이것과 동일한 방식으로 세그먼트 트리를 사용해서 배열의 뒤쪽부터 탐색하며 탐색한 값을 세그먼트 트리에 업데이트해주고,

현재 칸의 값이 k라면 0~k-1까지의 구간합을 구해주면 k보다 작은 수의 개수가 된다.

 

 

 

import sys
input = sys.stdin.readline

n = int(input())
input_arr = list(map(int, input().split()))

dict = {v:i for i,v in enumerate(sorted(input_arr))}
arr = [dict[x] for x in input_arr]

size = 1
while size<n:
    size *= 2

segtree = [0] * (size*2)

# 탐색한 값을 세그먼트 트리에 업데이트
def update(k):
    k += size
    while k>0:
        segtree[k] += 1
        k //= 2

# 0~k-1 까지의 누적합(k보다 작은 수의 개수)
def query(left, right):
    result = 0
    left += size
    right += size
    while left <= right:
        if left % 2 == 1:
            result += segtree[left]
            left += 1
        if right % 2 == 0:
            result += segtree[right]
            right -= 1
        left //= 2
        right //= 2
    return result

answer = 0

for i, k in enumerate(reversed(arr)):
    update(k)
    answer += query(0,k-1)

print(answer)