[백준] 7578번 : 공장

7578번: 공장

7578번: 공장

📄 문제개요

라인 A와 라인 B가 있을때 라인 A와 B에는 N개의 기계가 각각 있다고 하고, 직선으로 각각의 기계를 1:1 매칭 하였을때, 겹치는 선분의 개수를 구하는 문제이다. 1:1 매칭은 같은 유니크한 숫자를 매칭시킨다.

🤔 문제분석

라인 A의 기계들을 리터레이션 하는데, 하나씩 연결해보면서, 겹치는 선분이 있는지 확인한다.

B의 위치를 알기위해서는 딕셔너리 자료구조를 활용하여 위치를 파악한다.

📝 의사코드

1. A의 배열의 값을 순회한다.
   1. 딕셔너리 자료구조로 B에서의 현재위치를 찾는다.
   2. 현재위치 +1, N-1까지 기계들이 이미 연결되어 있는지 확인 한다. ( Query )
   3. 쿼리의 결과값을 ans 에 누적한다.
   4. 현재 위치를 연결했다는것을 표기한다. ( Update )
2. 리터레이션이 끝나면 ans을 출력한다.

💻 코드

import sys

input = sys.stdin.readline
N = int(input())

temp_A = list(map(int, input().split()))
temp_B = list(map(int, input().split()))
tree = [0 for _ in range(4*N)]

B = {}

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

def update(start, end, node, idx):
    if idx < start or idx > end:
        return
    
    tree[node] += 1
    
    if start == end:
        return
    
    mid = ( start + end ) // 2
    update(start, mid, node * 2, idx)
    update(mid + 1, end, node * 2 + 1, idx)

def query(start, end, node, left, right):
    if left > end or right < start:
        return 0
    
    if start >= left and end <= right:
        return tree[node]
    
    mid = ( start + end ) // 2
    lsum = query(start, mid, node * 2, left, right)
    rsum = query(mid + 1, end, node * 2 + 1, left, right)
    return lsum + rsum

ans = 0

for key in temp_A:
    ans += query(0, N-1, 1, B[key] + 1, N-1)
    update(0, N-1, 1, B[key])
    
print(ans)

🎯 피드백 및 개선사항

처음에 문제를 접할때 A의 오른쪽과, B의 왼쪽, B의 오른쪽과 A의 왼쪽을 모두 고려한 코드로 작성하였다.

그리고 중복된 부분을 제거 시키는 방식으로 문제를 해결하였는데, 시간복잡도와 메모리복잡도 모두 초과 판정을 받았다.

처음에 연결되지 않는 상태라고 가정을하고 생각을해보았다. 그리고 이미 연결된 부분을 확인하고 누적하고, 자기자신을 연결 되었다고 업데이트한다면, 빠르게 문제를 해결 할 수 있었다.

❓다른사람은 어떻게 풀었을까?

팬윅트리로 문제를 해결하신 분이 있다.

def update(i):
  while i<M:
    fen[i] += 1
    i += i&-i

def SUM(i):
  S = 0
  while i:
    S += fen[i]
    i -= i&-i
  return S

N = int(input()); M = 1<<19

D1,D2 = [[*map(int,input().split())] for i in range(2)]
Index = [0]*(1<<20)
for i in range(N):
  Index[D1[i]] = i+1

fen = [0]*M
result = 0

for i in range(1,N+1):
  idx = Index[D2[-i]]
  result += SUM(idx)
  update(idx)
print(result)