[BOJ/python]2370번 시장 선거 포스터

백준 2370번 시장 선거 포스터 파이썬

문제 링크 - https://www.acmicpc.net/problem/2370

2370번: 시장 선거 포스터

좌표 압축을 이용하여 100,000,000 크기의 좌표를 모두 탐색하지 않도록 한다. 포스터의 개수가 총 10,000개 이므로 왼쪽 끝 위치, 오른쪽 끝 위치는 최대 20,000개의 다른 좌표로 표현할 수 있다.

1. 풀이

• 포스터의 양쪽 끝 좌표를 L 배열에 저장한다.
• 포스터의 양쪽 끝 좌표를 따로 plane 배열에 저장하고 중복되는 좌표를 삭제 후 정렬한다.
• plane 배열에 저장된 좌표만 사용해서 포스터의 위치를 표현할 수 있다는 점을 이용해 딕셔너리에 현재 좌표 값을 key, 새로운 좌표(인덱스)를 value 로 저장한다.
• 전체 좌표를 answer 배열로 압축했다.
• answer 배열에 먼저 붙인 포스터부터 차례대로 새롭게 구한 왼쪽 끝 좌표(dl)에서 오른쪽 끝 좌표(dr)까지 모두 현재 포스터의 인덱스(i)로 저장한다.
• answer 배열에는 보이는 포스터의 인덱스만 저장되어 있다. visited 딕셔너리를 이용하여 포스터의 총 개수를 출력한다.

위와 같이 주어진 예제에서 0-7까지의 연속하는 수열로 5개의 포스터의 양 끝 좌표(10개)를 표현할 수 있다.

2. 코드

#시장 선거 포스터
#좌표 압축
#220708 poolc study, try, 
import sys
input = sys.stdin.readline

N = int(input())
L = []
plane = []
for _ in range(N):
    l, r = map(int, input().split())
    plane.append(l)
    plane.append(r)
    L.append([l,r])

setPlane = set(plane)
plane = list(setPlane)
plane.sort()

dictPlane = {}
for i in range(len(plane)):
    val = plane[i]
    dictPlane[val] = i

answer = [-1 for _ in range(len(plane))]
for i in range(N):
    l,r = L[i]
    dl, dr = dictPlane[l], dictPlane[r]
    
    for k in range(dl,dr+1):
        answer[k] = i
        
visited={}
for i in range(len(answer)):
    visited[answer[i]]=1

print(len(visited))