백준 11663 선분 위의 점(파이썬) 이분 탐색

 

11663번: 선분 위의 점 (acmicpc.net)

11663번: 선분 위의 점

이분 탐색 문제이다.

처음에는.. 아 for문 돌리면서 풀어야할텐데 이걸 어떻게 이분탐색으로 풀지? 고민이 많았는데

어차피 가장 큰값과 작은 값에 해당하는 인덱스를 알면 거기서 빼기만 하면 되니까 이분탐색이 되겠구나! 하는 접근방법으로 다가갔다.

그랬더니 정답은 나왔는데....

<틀린 코드>

import sys
N, M = map(int,input().split())
dots = list(map(int,sys.stdin.readline().split()))
for i in range(M):
    start, end = 0, N - 1
    a, b = map(int, input().split())
    while start <= end:
        mid = (start + end) // 2
        if a > dots[mid]:
            start = mid + 1
        else:
            end = mid - 1
            res = mid
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if b >= dots[mid]:
            start = mid + 1
            res2 = mid
        else:
            end = mid - 1
    print(res2 - res + 1)

이렇게 제출했는데 틀렸다고 나온 것이다.. 시간초과도 아니고 왜 틀렸다고 나왔을까...

했더니, 1.dot이 순서대로 나온다는 보장이 없어서 sort를 해줬어야 함

2.res, res2를 잘못 설정해줌

이렇게 크게 두가지 이유가 있었다...

그래서 고친 코드는.. 

<고친 코드>

import sys
N, M = map(int,sys.stdin.readline().split())
dots = list(map(int,sys.stdin.readline().split()))
dots.sort()
def dot_min(a):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if a > dots[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1
def dot_max(b):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if b >= dots[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return end
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    print(dot_max(b) - dot_min(a) + 1)

이렇게 된다.

우선 이분탐색에서 가장 중요한 키포인트는

1.각각의 이분탐색 식을 함수로 만들어서 필요할 때만 불러와 코드를깔끔+ 시간초과 피한다.
2.sys.stdin.readline()사용해야 시간초과 뜨지 않음
3.return해주는 값을 제대로 설정해야 한다.

 

사실 다 중요한 것 같지만... 계속 연습을 하자ㅏ...