[Algorithm🧬] 백준 5926 : Cow Lineup

문제
한글문제

문제

농부 존은 소유하고 있는 소들의 사진을 찍기 위해 전문 사진 작가를 고용했다. 다양한 품종의 소를 소유하고 있는 존은 한 장의 사진에 모든 종의 소가 포함 되길 원한다.
|
N마리의 소가 모두 라인에 맞춰(즉, Y 좌표는 고정) 다양한 위치(즉, X 좌표로 값은 정수 값임)에 서 있다. 그리고 소들은 정수 값의 품종 아이디를 목에 걸고 있다. 존은 연속된 범위의 사진을 찍을 계획이다. 사진 비용은 크기에 비례한다. 즉, X 좌표의 범위가 작을수록 비용은 저렴해진다.
|
당신이 할 일은 존이 한 장의 사진에 모든 품종의 소들이 적어도 한 마리씩은 포함될 수 있게 하는 최소 비용을 계산하는 것이다.

입력

첫 번째 줄에 소들의 수 N이 입력된다. (1≤N≤50,000)
두 번째 줄부터 N개 줄에 걸쳐 소의 위치 (X 좌표)와 소의 품종 아이디(ID)가 공백으로 구분되어 입력된다. (1≤X, ID≤1,000,000,000)

6
25 7
26 1
15 1
22 3
20 1
30 1

출력

모든 품종이 포함되는 X 좌표의 최소 범위를 출력하라.

4

import sys
import copy

readl = sys.stdin.readline

n = int(readl())
cows = [list(map(int, readl().split())) for _ in range(n)] # x 좌표, 번호
cows.sort()


# 소의 종류를 관리하기 위해서 dictonary 로 관리
dict = {}

for x, num in cows:
    if not num in dict.keys():
        dict[num] = 0
    dict[num] += 1

종류 = len(dict)

copy_dict = copy.deepcopy(dict)



left = 0
right = n - 1

# left 보다 앞쪽에 겹치는 종류의 소가 하나도 없을 때까지 left 땡기고
while left < n - 종류 and dict[cows[left][1]] > 1:
    dict[cows[left][1]] -= 1
    left += 1
# right 보다 뒷쪽에 겹치는 종류의 소가 없을 때까지 right 땡김
while 종류 <= right and dict[cows[right][1]] > 1:
    dict[cows[right][1]] -= 1
    right -= 1


dist = cows[right][0] - cows[left][0]

# print(left, right)

# 근데...! index 차가 거리였다면 위에서 끝내도 되는데,
# 여기서는 x 좌표가 있으므로 left 먼저 땡긴것과 right 먼저 땡긴 것의 결과가 차이나서
# 그 둘을 비교하기 위해 한번 더 돌림.
# 솔직히 이 코드 넘 구린디.........
left = 0
right = n - 1

while 종류 <= right and copy_dict[cows[right][1]] > 1:
    copy_dict[cows[right][1]] -= 1
    right -= 1

while left < n - 종류 and copy_dict[cows[left][1]] > 1:
    copy_dict[cows[left][1]] -= 1
    left += 1

dist = min(dist, cows[right][0] - cows[left][0])
print(dist)

합쳐보려고 했으나 실패한 코드

left = 0
right = n - 1

startX = cows[left][0]
endX = cows[right][0]

while left < n - 종류 and 종류 <= right:
    거리 = cows[right][0] - cows[left][0]
    if dict[cows[left][1]] > 1 and dict[cows[right][1]] > 1:
        if cows[left][0] - startX > endX - cows[right][0]:
            dict[cows[left][1]] -= 1
            left += 1
        elif cows[left][0] - startX == endX - cows[right][0]:
            # 여기서 left, right 하나씩 떙겨서 검사해보려고 했는데
            # 만약 그 다음 것도 같으면..? 계속계속 끝까지 검사해야함... oh no
        else:
            dict[cows[right][1]] -= 1
            right -= 1
    elif dict[cows[left][1]] > 1:
        dict[cows[left][1]] -= 1
        left += 1
    elif dict[cows[right][1]] > 1:
        dict[cows[right][1]] -= 1
        right -= 1
    else:
        break

print(cows[right][0] - cows[left][0])