[백준, 파이썬, 7795번] 먹을 것인가 먹힐 것인가

 

풀이

 

• 해당 문제는 단순히 2중 for문으로 해결하기엔
• 불필요한 시간이 많이 사용될 것 같아 이분 탐색 알고리즘으로 해결
• 우선 받아오는 A,B의 입력 값을 sorted로 정렬해야 찾은 인덱스 아래의 값들은 모두
• 해당 값보다 작다고 판단할 수 있기에 오름차순 정렬
• 이후 이분 탐색으로 해결하는데 처음 제출한 값이 25%에서 에러가 난 이유를 확인해보니
• elif 문에 result에 더하는 값을 그냥 mid+1로 제출 하다보니 틀렸다
• 반례로는 
  • 1
    1 2
    3
    1 3
  • 위와 같이 제출해보니
  • mid가 1로 되어져 결과가 2로 되어지는 것을 확인 후 
  • e와 s중 작은 값 +1 로 변경 후 해결

 

import sys

inpyt = sys.stdin.readline

for _ in range(int(input())):

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

    n_li,m_li = sorted(list(map(int,input().rstrip('\n').split()))),sorted(list(map(int,input().rstrip('\n').split())))

    # 1 1 3 7 8

    # 1 3 6

    result = 0

    for i in n_li:

        s,e = 0,m-1

        mid = 0

        while e>=s:

            mid = (s+e)//2

            if i > m_li[mid]: s = mid+1

            else: e = mid-1

        if mid == 0 and i > m_li[0]: result += 1

        elif mid != 0: result += min(s,e)+1

    print(result)