11663 : 선분 위의 점(Python)

https://www.acmicpc.net/problem/11663

 

1. 틀린 풀이 및 알아갈 점

def binary_search(list1, target):
    left, right = 0, len(list1)-1
    
    while left <= right:
        mid = (left+right)//2
        
        if target < list1[mid]:
            right = mid-1
        elif target > list1[mid]:
            left = mid+1
        elif target == list1[mid]:
            return mid
    return right

n,m = map(int, input().split())
list1 = list(map(int,input().split()))
list1.sort()
for _ in range(m):
    a,b=map(int, input().split())
    n1 = binary_search(list1,a)
    n2 = binary_search(list1,b)

    if a in list1 or b in list1:
        print(n2-n1+1)
    else:
        print(n2-n1)

 

틀린 이유 및 알아갈 개념(if문과 시간 복잡도, if ~ in list) 정리

 

- 틀린이유

비교되는 점 2개 중 하나 이상이 주어진 n개의 점과 같은 위치로 주어질 때 중복되는 값을 계산하지 못했다. 이를 if ~ in list 구문으로 해결하려했지만 이렇게 되버리면 시간 초과가 되버리기 때문에 문제를 맞추지 못했다.

 

- 알아갈 개념

어제 이거 때문에 꽤나 삽질을 한 것 같은데 삽질을 하던 도중 알아가면 좋을 개념 2가지에 대해 소개하겠다. 하나는 문제의 맞춤 유무를 판별지었던 if문과 시간 복잡도의 관련성이고 두 번째는 if ~ in list 구문에서 내가 잘못 썼던 개념에 대해 짚고 넘어간다.

 

https://yongbbbba.github.io/til/2021/02/17/if/

[알고리즘] if문과 시간 복잡도

 

전체적인 그림은 그리지 못하고 순간의 에러를 처리하기 위해 방어적으로 if문을 남발하는 것은
스파게티 코드의 근원이다.

 

예를 들어

if ~ :
    if ~ :
        if ~ :
    
    else:

 

대충 이런 식으로의 딱봐도 깔끔하지 않은 형태의 코드일 것이다.

내가 if 문과 시간 복잡도에 대해 살펴본 이유는 시간 초과를 야기했다고 생각했던 if ~ in list 구문이 실제로 얼마나 시간 복잡도에 영향을 미치는지 궁금해서이다.

 

위 블로그를 참고해서 결론부터 얘기하자면 if문은 시간 복잡도에는 영향을 미치지 않는다고 한다.

그러나 if문이 많아지면 프로그램 성능 자체에는 영향을 미칠 수도 있다고 한다. big-O 개념은 input data size은 n에 의해 측정되는 시간의 복잡도를 나타내는 것이기 때문에 if문이 많아지는 것에 대해 big-O에는 영향을 미치지 않는다고 한다. 오히려 binary search처럼 if문을 잘 쓰면 연산량을 줄여줄 수 있다고 한다.

 

 

 

https://stackoverflow.com/questions/21344842/if-a-or-b-in-l-where-l-is-a-list 

 

내가 처음에 실수했던 부분은 체크해야 할 요소인 a,b에 대해 if a or b in list1: 으로 했다는 것이었다. 내가 의도했던 바는 a나 b가 list1에 있을 경우 if문을 실행하시오였지만 실제로는 그렇게되지 않았다. 실행한 부분이 모두 if문으로 실행되었고 위의 stackoverflow를 참고한 결과 if a in list1 or b in list1으로 해야 내가 원하는 결과를 얻을 수 있다는 것을 알게 되었다.

 

 

 

2. 정답 풀이

이진 탐색을 이용해 문제 풀 때 항상 주의할 점은 리스트를 정렬시킨 뒤 탐색을 돌려야 한다는 것이다. 

 

n,m = map(int,input().split())
list1 = list(map(int,input().split()))
list1.sort()
list2 = []
for _ in range(m):
    list2.append(input().split())

def first_point(target, list1):
    left, right = 0, len(list1)-1
    
    while left<=right:
        mid = (left+right)//2
        
        if list1[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return right+1
    
def last_point(target, list1):
    left, right = 0, len(list1)-1
    
    while left<=right:
        mid = (left+right)//2
        
        if list1[mid] > target:
            right = mid-1
        else:
            left = mid+1
    return right
    
for i in range(m):
    a,b=first_point(int(list2[i][0]), list1), last_point(int(list2[i][1]), list1)
    print(b-a+1)

 

전체적인 구조를 만드는 것은 할만했는데 이진 탐색 과정에서 right와 left를 어디에 두는지, mid값과 겹칠 경우 list요소보다 target값이 클 때를 고를건지 작을 때를 고를 건지 구분하는 과정이 쉽지않다.

 

 

이분탐색 아직도 정복은 먼 것 같은디..?