-
[BOJ/python]2370번 시장 선거 포스터알고리즘/BOJ 2022. 7. 18. 16:09
백준 2370번 시장 선거 포스터 파이썬
문제 링크 - https://www.acmicpc.net/problem/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))
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]1655번 가운데를 말해요 (0) 2022.08.08 [BOJ/python]2836번 수상 택시 (0) 2022.07.21 [BOJ/python]14427번 수열과 쿼리 15 (0) 2022.07.18 [BOJ/python]1106번 호텔, knapsack 알고리즘 설명 (1) 2022.07.15 [BOJ/python]2015번 수들의 합 4 (0) 2022.07.15