99클럽 코테 스터디 3일차 TIL [백준 11663] 선분 위의 점

 

 

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

 

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

 

입력	출력
5 5 1 3 10 20 30 1 10 20 60 3 30 2 15 4 8	3 2 4 2 0

---

풀이방식

각 입력위치에 해당하는 위치마다 얼만큼 입력들이 있을 수 있는지 미리 DP로 계산한 다음에 넣어둔다.

이후에 선분 길이가 주어지면 시작지점이 DP내 어디에 위치할지 왼쪽 기준으로 알아내고, 끝 지점은 오른쪽 기준으로 알아낸다.

(사실 이 문제에서는 같은 입력값이 중복으로 나오진 않기에 굳이 왼쪽, 오른쪽을 나눌 필요는 없었을 것이다)

 

그리고 그걸 3가지 경우를 통해 계산을 해야 하는데, 처음에 나는 이 중 2가지를 계속 빼먹어서 애를 먹었다.

- 입력위치들 내에 선분의 시작과 끝이 다 있는 경우.

- 선분의 시작과 끝이 입력위치들을 초과하는 경우.

- 선분의 시작과 끝중 일부만 입력위치에 걸치는경우. 

깨달은점

1. bisect_left, bisect_right 는 현재 위치를 반환하지 않고, 삽입될 위치를 반환한다. 따라서 -1을 각 해주되, 입력 시작지점보다 먼저 선분이 시작된 경우까지 고려해서 코드를 짜야 한다.

 

2. 입력값들의, 열린구간-닫힌구간에 대해 다시 한번 잘 생각하고, 미리 첫 제출 할 때부터 반례를 몇가지 생성 해야겠다.

내가 만든 반례는 아래와 같다.

4 4
4 6 8 10
5 8
1 4
8 15
15 20

1 1
9
2 3

풀이 코드

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

P,L = map(int,input().split())
Points = list(map(int,input().split()))

DP = {0:0}
count = 1
Points = sorted(Points)
arr = []
for p in Points:
    DP[p] = count
    count += 1
for _ in range(L):
    cnt = 0
    S, E = map(int,input().split())
    S = bisect_left(Points,S) - 1
    E = bisect_right(Points,E) - 1
    if(S >= 0 and E >= 0):
        cnt += DP[Points[E]] - DP[Points[S]]
    elif(E >= 0):
        cnt += DP[Points[E]]
    arr.append(cnt)

for a in arr:
    print(a)