사용자 도구

사이트 도구


ps:problems:boj:1517

버블 소트

ps
링크acmicpc.net/…
출처BOJ
문제 번호1517
문제명버블 소트
레벨골드 1
분류

Inversion Counting

시간복잡도O(nlogn)
인풋사이즈n<=500,000
사용한 언어Python
제출기록86980KB / 2804ms
최고기록2644ms
해결날짜2021/05/26
태그

38단계

풀이

  • 말을 살짝 꼬아놨지만 결국은 Inversion의 갯수를 세는 문제
  • Inversion Counting에서 설명했듯, 머지소트에 기반한 방식과 Order Statistic Tree에 기반한 방식으로 풀 수 있다.
  • 문제가 여기에서 조금 확장되면 머지소트을 사용하는 방법은 적용하기가 어렵거나 속도가 느리거나 하지만, 이 문제에서만은 머지소트 방법이 더 빠르게 동작했다.
  • 그래서 두가지 코드를 모두 적었다. 시간 복잡도는 둘 다 O(nlogn).

코드

코드 1 - 머지소트

"""Solution code for "BOJ 1517. 버블 소트".

- Problem link: https://www.acmicpc.net/problem/1517
- Solution link: http://www.teferi.net/ps/problems/boj/1517
"""


def sort_and_count_inversion(list_):
    if len(list_) <= 1:
        return 0
    mid = len(list_) // 2
    left, right = list_[:mid], list_[mid:]
    inversion_count = (sort_and_count_inversion(left)
                       + sort_and_count_inversion(right))
    l_size, r_size = mid, len(right)
    i = j = 0
    ret = []
    while True:
        try:
            if left[i] <= right[j]:
                ret.append(left[i])
                i += 1
            else:
                ret.append(right[j])
                j += 1
                inversion_count += l_size - i
        except IndexError:
            break            
    list_[:] = ret
    list_.extend(left[i:])
    list_.extend(right[j:])
    return inversion_count


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    print(sort_and_count_inversion(A))


if __name__ == '__main__':
    main()

코드 2 - Order Statistic Tree

"""Solution code for "BOJ 1517. 버블 소트".

- Problem link: https://www.acmicpc.net/problem/1517
- Solution link: http://www.teferi.net/ps/problems/boj/1517
"""

from teflib import fenwicktree


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    
    compress_map = {x: i for i, x in enumerate(sorted(set(A)))}
    comp_a = [compress_map[x] for x in A]
    ost = fenwicktree.OrderStatisticTree(len(compress_map))
    answer = 0
    for a_i in reversed(comp_a):
        answer += ost.count_less_than(a_i)
        ost.add(a_i)
        
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Y​ Z F B W
 
ps/problems/boj/1517.txt · 마지막으로 수정됨: 2021/05/26 14:40 저자 teferi