7579 - 공장

안녕하세요. 꼬동입니다.

 

즐거운 연휴 첫 날 여러분은 어떻게 지내시고 계신가요 !

 

저는 연휴의 시작을 알고리즘 문제와 함께합니다.

 

희희

 

오늘 문제는 공장이라는 문제입니다.

 

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

7578번: 공장

---

이 문제는 https://ggodong.tistory.com/301와 동일한 알고리즘의 문제인데요.

 

사실 문제는 이 문제를 보고 Inversion Counting을 생각해낼 수 있는지가 가장 큰 키 포인트입니다.

 

처음에 보고 LIS도 머릿 속에서 지나갔는데, LIS는 최장 증가하는 부분 수열을 구하기 위한 알고리즘이고, 해당 문제는 얼마나 꼬여있는지를 알아 내는 거니 문제의 결이 다르죠.

 

안그래도 질문에서 LIS 어쩌구 질문이 있더라고용.

 

해당 질문에 답이 될 수 있겠죠.

 

어쨌든 문제를 풀어봤습니다.

---

132 392 311 351 231

392 351 132 311 231

 

윗 숫자를 아래 숫자와 매칭시켜 아래 숫자 인덱싱 기준으로 배열을 만들어 봅시다.

 

[2, 0, 3, 1, 4]

 

문제에서 이렇게 꼬여있는걸 직선으로 만들길 원합니다. 즉, 각 숫자가 제 위치에 찾아가면 되는거죠.

 

[0, 1, 2, 3, 4] => 이렇게요.

 

그럼 어디서 많이 본 문제죠?

 

Inversion Counting 입니다.

 

0부터 시작해서 해당 인덱스 기준으로 끝까지 자기보다 작은 수를 찾으면 되는겁니다.

 

[2, 0, 3, 1, 4]

 

여기서 2를 기준으로 뒷 인덱스(1 ~ 4)를 비교하면 자기보다 작은 수, 0 / 1, 2개죠 ? 이런식으로 체크하면 되는데, 이를 하기 위해서 세그먼트 트리와 머지소트를 이용할 수 있습니다.

---

import sys

input = sys.stdin.readline

def ordering():
    for i, v in enumerate(B):
        B_O[v] = i

    for i, v in enumerate(A):
        A_O.append([i + 1, B_O[v]])
    

def check(n, s, e, l, r):
    if e < l or r < s:
        return 0

    if l <= s and e <= r:
        return TREE[n]

    m = (s + e) // 2
    return check(n * 2, s, m, l, r) + check(n * 2 + 1, m + 1, e, l, r)


def update(n, s, e, i):
    if i < s or e < i:
        return TREE[n]

    if s == e == i:
        TREE[n] = 1
        return 1

    m = (s + e) // 2
    TREE[n] = update(n * 2, s, m, i) + update(n * 2 + 1, m + 1, e, i)
    return TREE[n]


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_O = []
B_O = [0] * 1000001

ordering()
A_O = sorted(A_O, key=lambda x: x[1])

TREE = [0 for _ in range(N * 4)]
result = 0

for a in A_O:
    i, _ = a
    result += check(1, 1, N, i + 1, N)
    update(1, 1, N, i)

print(result)

4초..

시간 넘 오래 걸려..

 

저희가 전에 세그먼트 트리 말고, Inversion Counting을 할 수 있었던 방법이 Merge Sort가 있었죠 ?

 

import sys

input = sys.stdin.readline

def ordering():
    for i, v in enumerate(B):
        B_O[v] = i

    for i, v in enumerate(A):
        A_O.append([i + 1, B_O[v]])


def mergeSort(s, e):
    global result
    if s >= e:
        return

    m = (s + e) // 2
    mergeSort(s, m)
    mergeSort(m + 1, e)

    l = idx = s
    r = m + 1

    while l <= m and r <= e:
        if A_O[l] < A_O[r]:
            TMP[idx] = A_O[l]
            l += 1
        else:
            TMP[idx] = A_O[r]
            r += 1
            result += m + 1 - l
        idx += 1

    while l <= m:
        TMP[idx] = A_O[l]
        l += 1
        idx += 1
    
    while r <= e:
        TMP[idx] = A_O[r]
        r += 1
        idx += 1
    
    for i in range(s, e + 1):
        A_O[i] = TMP[i]


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_O = []
TMP = [0] * 1000001
B_O = [0] * 1000001

ordering()
A_O = list(map(lambda x: x[0], sorted(A_O, key=lambda x: x[1])))

result = 0
mergeSort(0, N - 1)
print(result)

1.3초 !

굳

---

이제 게임하러 가야지 ~

 

좀보이드 추천 받았는데 한 번 설치해봐야겠네요 !

좀비 무셔

---

이상 7579 - 공장였습니다. ^_^