[백준] 7578번 : 공장 (Python)

문제

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

---

문제 요약

 

A 열에 위치한 기계, B 열에 위치한 기계의 식별번호가 주어진다.

각 기계는 유일한 식별번호를 가지며, A 열의 특정 식별번호를 가진 기계는 B 열에 반드시 존재한다. (짝을 이룬다)

A열, B열의 기계들에 대해, 식별번호가 같은 기계끼리 모두 연결했을 때 발생하는 교차하는 선 쌍의 개수를 찾는 문제이다.

(중요) 교차점 을 구하는 문제가 아니다! (선 N개가 한 점에서 교차하는 경우를 생각하지 않아도 된다.)

---

문제에서 체크할 것들

입력값의 특성

 

• 기계의 개수 $N$ : $1  \leq N  \leq 500,000$

→ $O(NlogN)$ 알고리즘으로 해결해야 하구나! ($O( N^{2} )$ 알고리즘으로는 불가)

• 기계의 식별번호 $K$ : $0 \leq K \leq 1,000,000$

→ 큰 수를 다루는 문제는 아니구나!

---

문제 해결을 위한 핵심 키워드

자료구조의 적절한 선택 + 교차 조건에 대한 수학적 이해 + Segment Tree 적용 및 구현

---

풀이

1. B열의 각 원소 개수 만큼 Leaf 노드를 가지는 Segment Tree 배열 $tree$ 를 선언.
   • 이 배열의 Leaf 노드에는 해당 원소(기계)가 A열과 대응되었는지 여부를 저장. (A열과 대응됨 = 1, 초기값 0)
   • $tree$ 는 구간 합 세그먼트 트리로 구축.
2. A열의 기계를 차례대로 순회 ($0$ ~ $N - 1$)
3. A열에서 선택한 기계의 B열에서의 위치 탐색
4. 교차점 개수 계산 : B열에서 해당 기계의 위치 ~ 우측 끝($N - 1$) 구간 합을 계산.
   • 이 구간 합 값이 곧 교차점 개수를 뜻함.
5. 해당 기계의 대응 여부 업데이트 및 Segment Tree 갱신

---

왜 대응 지점 ~ 우측 끝 구간의 연결 여부만 보고 답을 구하는가? (대응 지점의 좌측 부분은 왜 고려하지 않는가)

A열의 왼쪽(인덱스 0)부터 오른쪽으로 차례대로 기계를 선택해서 선을 긋는다.

따라서 B열의 특정 기계에 이미 방문 표시(1)가 되어 있다는 것은, 해당 기계는 A열에서는 반드시 현재 선택한 기계보다 왼쪽에 있던 기계라는 뜻이다.

 

• 교차 조건: $A_i < A_j$ 이면서 $B_i > B_j$ 일 때

교차 조건은 위와 같다.

A열에서는 나보다 왼쪽에 있는데, B열에서는 나보다 오른쪽에 있는 경우에 교차하게 된다.

 

그렇기 때문에 B열의 현재 기계 위치 기준으로 우측 구간에 있는 '이미 방문한 기계의 수'가 곧 현재 기계와 교차하는 선분의 개수가 된다.

 

---

A열에서 선택한 기계의 B열에서의 위치 탐색 방법

Dictionary 자료구조 이용

• 딕셔너리 구축 시에는 $O(N)$
• 리스트 탐색 $O(N)$ → $O(1)$으로 개선

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

hashmap = {}
for i in range(N):
    hashmap[B[i]] = i
    
# 추후 순회할 때, 아래 코드와 같이 B열에서의 기계 위치를 찾아냄.

for i in range(N):
    target = hashmap[A[i]]

---

전체 소스 코드

import sys

input = sys.stdin.readline

N = int(input())

power_of_two = 1
while power_of_two < N:
    power_of_two *= 2

SIZE = power_of_two

tree = [0] * (2 * SIZE)
hashmap = {}
A = list(map(int, input().split()))
B = list(map(int, input().split()))

for i in range(N):
    hashmap[B[i]] = i


def update(index):
    i = index + SIZE
    tree[i] = 1
    i //= 2
    while i > 0:
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2


def search(left, right):
    ret = 0
    l = left + SIZE
    r = right + SIZE
    while l <= r:
        if l % 2 == 1:
            ret += tree[l]
            l += 1
        if r % 2 == 0:
            ret += tree[r]
            r -= 1
        l //= 2
        r //= 2
    return ret


result = 0
for i in range(N):
    target = hashmap[A[i]]
    result += search(target, N - 1)
    update(target)
print(result)

 

세그먼트 트리는 반복문을 이용한 Bottom-Up(비재귀) 방식으로 구현했다.

트리를 포화 이진 트리(Full Binary Tree) 형태에 가깝게 만들어 인덱스 계산을 쉽게 하기 위해, 리프 노드의 개수를 N 이상의 가작 작은 2의 거듭제곱 수로 패딩(Padding)했다.

---

느낀점

• Dictionary 자료 구조를 이용하는 판단
  • A열의 기계가 B열 어디에 있는지 $O(1)$ 시간에 찾을 수 있어야 한다.
• 교차 조건에 대한 수학적 이해
  • 선택한 기계를 대응시킬 경우, 현재 기계의 B열 위치보다 오른쪽에 있는 기계들 중 이미 연결된 기계와 반드시 교차한다.
• Segment Tree 적용 및 구현

이러한 능력이 필요한 것 같다.

 

이 중 특히, 교차 조건에 대해 깨닫는 데에 오래 걸렸던 것 같다.