백준 12099 : 점심메뉴 (Python)

본문 링크

import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
L=[]

for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])

L.sort()
# 매운맛의 범위에서 최소인덱스와 최대인덱스를 찾고 그곳에서 반복문을 돌려 count를 센다.
# 총 2개의 while문과 하나의 반복문이 필요하다.

for i in range(Q):
    u,v,x,y=map(int,input().split())

    start=0 ; end=N-1
    left_index=0 ; right_index=0
    while start<=end:
        mid=(start+end)//2
        if L[mid][0]<u:
            start=mid+1
        else:
            end=mid-1

    left_index=start
    start=0 ; end=N-1
    while start<=end:
        mid=(start+end)//2
        if L[mid][0]<=v:
            start=mid+1
        else:
            end=mid-1
    right_index=end

    count=0
    for i in range(left_index,right_index+1):
        if x<=L[i][1]<=y:
            count+=1

    print(count)

📌 어떻게 접근할 것인가?

먼저 문제에서 주어지는 수의 범위를 보자.
1 ≤ N ≤ 10만 , 1 ≤ Q ≤ 5000 이다. 이 범위를 완전탐색을 통해 풀기에는 시간이 매우 많이 소모된다.

따라서 이분탐색을 사용하기로 했다.

📌 이분탐색을 어떻게 할것인가?

이분탐색은 어떤 조건을 만족하는 x의 최대 , 최소값을 구할 때 쓰인다.
하지만 이 문제에서는 u, v, x, y 와 같이 여러가지 변수가 주어지기에
무슨 값을 찾기 위해 이분탐색을 쓸것인가? 에 대한 의문이 생긴다.

하지만 코드에서 꼭 이분탐색을 한번만 사용할 필요는 없다.
즉 내가 필요한 값을 찾을때 언제든지 이분탐색을 사용가능하다는것을 잊지 말아야한다.

먼저 리스트 L를 정렬한 후 매운맛을 먹을수 있는 최소인덱스와 최대인덱스를 구한다.

총 2번의 이분탐색으로 구한후 , 최소인덱스와 최대인덱스 사이에서 먹을수 있는 단맛을 구하면 된다.

따라서 총 이분탐색을 2번 , 반복문을 1번 사용하게 된다.
시간초과가 날 수있지않을까? 라고 생각했지만 적어도 완전탐색보다 빠르고 시간초과는 발생하지 않았다.

✅ 코드에서 중요한 부분

• 이분탐색은 꼭 한번만 할 필요는없다. 필요에따라서 여러번 해도되고 반복문도 같이 사용가능하다.
• 최소 인덱스를 구할때는 이분탐색후 start 변수를 저장한다.
• 최대 인덱스를 구할때는 이분탐색후 end 변수를 저장한다.