[BOJ] [Python] 11663번 : 선분 위의 점

예를 들어보자.

(아래는 백준 예제 입력 1의 일부이다.)

 

5 1

1 3 10 20 30

1 9

 

현재 점의 위치는 1, 3, 10, 20, 30이다.

선분의 시작점은 1, 끝점은 9이다.

 

점의 위치 상에서 선분의 위치를 찾아줘야 한다.

 

점의 위치 상에서,

선분의 시작점은 선분의 시작점보다 크거나 같은 최솟값,

선분의 끝점은 선분의 끝점보다 작거나 같은 최댓값을 찾아주면 된다.

 

 

점의 위치 상에서 선분 시작점과 끝점 찾기

 

 

따라서 각각 1과 3이다.

(전자는 tmp_s, 후자는 tmp_e)

 

여기서 주의할 점은 범위이다.

 

 

첫 번째

선분의 시작점이 점의 가장 앞의 위치보다 왼쪽에 있을 때.

 

=>  tmp_s를 점의 가장 앞의 위치로 생각해주면 된다.

선분이 포함하는 최솟값이 가장 앞의 위치이기 때문이다.

 

 

첫 번째

 

 

두 번째

선분의 끝점이 점의 가장 끝 위치보다 오른쪽에 있을 때.

 

=> tmp_e를 점의 가장 끝 위치로 생각해주면 된다.

선분이 포함하는 최댓값이 가장 끝 위치이기 때문이다.

 

 

두 번째

 

 

세 번째

선분의 시작점과 끝점 모두 점의 가장 앞의 위치보다 왼쪽에 있을 때.

 

=> tmp_s는 점의 가장 앞의 위치로, tmp_e는 -1로 생각한다.

-1 + 0 + 1 = 0이기 때문이다.

 

포함하지 않는 위치여도 tmp_s를 0으로 했고,

계산을 위해 tmp_e는 -1로 하였다.

 

 

세 번째

 

 

네 번째

선분의 시작점과 끝점 모두 점의 가장 끝 위치보다 오른쪽에 있는 경우.

 

=> tmp_s는 가장 끝의 위치 + 1로,

tmp_e 점의 가장 끝의 위치로 생각한다.

 

세 번째와 마찬가지로 tmp_e의 값은 끝의 위치를 포함하지 않지만

계산을 위해 할당된 것이다.

 

 

네 번째

 

 

import sys
input = sys.stdin.readline

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


def BSearch(start, end):

    for target in start, end:
        check = False
        val = True

        if target == start:
            check = True

        low = 0
        high = len(li) - 1

        tmp_s = -1
        tmp_e = -1

        while low <= high:
            mid = (low + high) // 2

            if li[mid] == target:
                result.append(mid)
                val = False
                break

            elif li[mid] < target:
                tmp_e = mid
                low = mid + 1

            else:
                tmp_s = mid
                high = mid - 1

        if val:
            if check:
                if tmp_s == -1:
                    if target < li[0]:
                        tmp_s = 0
                    else:
                        tmp_s = len(li)

                result.append(tmp_s)

            else:
                result.append(tmp_e)


for _ in range(m):
    s, e = map(int, input().split())
    result = []

    BSearch(s, e)

    print(result[1] - result[0] + 1)

 

while문 밑에 조건문이 많아서 가독성이 좋지 않아보인다.

 

 

 

시간초과

 

시간초과 문제를 해결하기 위해서 2가지를 수정했다.

 

1. 처음에는 BSearch 함수를 두 번 호출하여, tmp_s와 tmp_e를 구하려고 했다.

하지만 함수 호출 자체에 시간이 걸리는 것 같아서 수정했다.

 

2. input이 최대 100,002이다. input에 sys.stdin.readline를 할당하였다.

 

 

for _ in range(m):
    s, e = map(int, input().split())

    first = BSearch(s, True)
    second = BSearch(e, False)