백준 17124번 문제(두 개의 배열) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

17124번: 두 개의 배열

 

정답 코드는 아래와 같습니다.

def findMin(d):
  curr = d[2]
  rst = 2
  if d[1] <= curr:
    curr = d[1]
    rst = 1
  if d[0] <= curr:
    curr = d[0]
    rst = 0
  return rst
 
def binary(item, B, start, end):
  diff = end - start
  if diff <= 1:
    return start
  mid = (start + end) // 2
  if item < B[mid]:
    return binary(item, B, start, mid)
  else: # item >= B[mid]
    return binary(item, B, mid, end)
 
def solve():
  n, m = [int(x) for x in input().split()]
  A = [int(x) for x in input().split()]
  B = [int(x) for x in input().split()]
  B.sort()
  s = 0
  for item in A:
    p = binary(item, B, 0, m)
    d = []
    d.append(abs(B[p-1] - item))
    d.append(abs(B[p] - item))
    d.append(abs(B[(p+1)%m] - item))
    idx = findMin(d)
    s += B[p + idx - 1]
  print(s)
 
t = int(input())
for _ in range(t):
  solve()

 

728x90

 

Binary search 또는 이분 탐색 이라고 하면 너무 어려운 느낌이 들지만, 사실 우리는 일상 생활에서 매우 자주 binary search를 활용하고 있습니다.

도서관에서 책을 찾는 것도 이분 탐색 문제의 일종이고, 병뚜껑 뒤에 적힌 숫자 맞추는 게임(업다운 게임)은 전형적인 이분 탐색 문제입니다.

이 문제도 전형적인 이분 탐색 문제이며 bisect 를 이용하지 않고 직접 구현하였기 때문에 binary search 함수를 지원하지 않는 언어를 사용하시는 분들도 참고하시면 도움이 될 것입니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=VxLEDVZKinA 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)