[Python] 백준 #11663- 선분 위의 점

문제

---

 

11663번: 선분 위의 점

코드

---

My answer(시간초과, 메모리 초과)

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

n,m=map(int,input().split())
point=list(map(int,input().split()))

# 반복문을 이용한 이진탐색(시간초과)
for i in range(m):
    a,b=list(map(int,input().split()))
    cnt=0
    for j in range(len(point)):
        start,end=a,b
        while(start<=end):
            mid=(start+end)//2
            if(mid==point[j]):
                cnt+=1
                break
            if(mid>point[j]):
                end=mid-1
            else:
                start=mid+1
    print(cnt)

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

n,m=map(int,input().split())

point=list(map(int,input().split()))
line=[map(int,input().split()) for i in range(m)]
    
# bisect를 이용한 이진탐색(메모리초과)
for i in range(len(line)):
	cnt=0
    for j in range(len(point)):
    	start,end=line[i]
        array=[i for i in range(start,end+1)]
        tmp=bisect_right(array,point[j])-bisect_left(array,point[j])
        if(tmp>0):cnt+=1
    print(cnt)

Another answer

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
point = list(map(int, input().split()))
point.sort()
line=[map(int,input().split()) for i in range(m)]

def binary_min(start, end, target):
    while start <= end:
        idx = (start + end) // 2
        mid = point[idx]
        
        if target > mid:
            start = idx + 1
        else:
            end = idx - 1
    return end + 1

def binary_max(start, end, target):
    while start <= end:
        idx = (start + end) // 2
        mid = point[idx]

        if target >= mid:
            start = idx + 1 
        else:
            end = idx - 1
    return end

for least, largest in line:
    start, end  = 0, len(point)-1 # index
    mini = binary_min(start, end, least)
    maxi = binary_max(start, end, largest)
    print(maxi - mini + 1)

풀이

---

우선 나는 그냥 각 선분마다, 선분이 시작점과 끝점을 start와 end로 두고 시작해서 각 point별로 모두 안에 있는지 없는지를 확인하는 이진탐색 코드를 bisect와 반복문을 이용해서 짜봤다. 그러나 각 선분마다 각 점을 모두 확인해야하기 때문에 이중반복문에다가 그 안에 이진탐색도 돌기 때문에 시간초과가 났다. bisect는 해당 범위를 나타내는 리스트를 생성하느라 메모리초과가 난 것 같다..시간을 단축할 방법을 모르겠어서 다른 코드를 참조하였고 아이디어 자체를 다르게 해야했다.

 

우선 각 선분을 돌면서 각 선분마다 몇개의 점이 돌아가는지를 반복문으로 하나씩 해결하는게 아니라 한번에 해결할 것이다. 

방법은 우선 점들을 정렬하고, 해당 선분에 포함되는 가장 작은점과, 가장 큰 점을 골라 그 사이에 있는 점들은 모두 포함된다는 것이다.

예를들어 point가 1,3,5 가있고 선분이 1-10이 있을 때, 내 코드같은 경우는 1,3,5 모두를 확인해야하지만, another answer은 1을확인하고 5를 확인해서 해당 인덱스 0번부터 2번이므로 총 3개 이런식으로 판단하는 것이다. 이는 포함되는 숫자가 많을 수록 효율적이게 된다. 내 코드는 반면 멍청해지고. 이제 코드를 해석해보겠다. 

우선 point들을 정렬해준다. 이후 2번의 이분탐색을 할건데, 하나는 시작점(선분에 포함되는 가장 작은 포인트)를 찾는 탐색과 끝점(선분에 포함되는 가장 마지막 포인트)를 찾는 탐색 총 2번이다. 

 

아래 그림에 두번의 탐색이 어떻게 수행됐는지 그려놨다. 

각 이진탐색의 함수안에서의 반환값과 조건을 유의해야할 것 같다.