[백준/Python] 17124번 - 두 개의 배열

문제

백준 17124번 - 두 개의 배열

해결 과정

• 이진탐색
• binary함수 : A의 i 값이 B의 몇 번째 값과 가까운지 찾아주는 함수
  • i,배열 B, 배열 B에서 어디서부터 어디까지 탐색할건지 start,end 값을 받는다.
  • end - start <= 1 start -> 즉 B배열에서 A의 i와 가장 가까운 값
  • B배열의 중간 값보다 작다면 start부터 중간까지 탐색
  • 크다면 중간부터 end까진 탐색
• diff배열에 p의 바로 앞, p, p의 바로 뒤 값을 넣는다.
• findMin함수: 배열에서 가장 작은 값의 인덱스를 출력해주는 함수
  • 차이가 가장 작은 값의 인덱스를 리턴
• result에 해당 값들을 더해준다.

시행착오

• 시간 초과 왜? -> 하나씩 비교하면 10억 넘어버림 -> 각각 서치하는 알고리즘은 안됨..

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())
    A_array = list(map(int, sys.stdin.readline().split()))
    B_array = list(map(int, sys.stdin.readline().split()))
    B_array.sort(reverse=True)
    C_array = []
    for i in range(n):
      for j in range(m-1):
        if abs(A_array[i] - B_array[j]) < abs(A_array[i] - B_array[j+1]):
          C_array.append(B_array[j])
          break
        elif abs(A_array[i] - B_array[j]) == abs(A_array[i] - B_array[j+1]):
          C_array.append(min(B_array[j],B_array[j+1]))
          break
        elif abs(A_array[i] - B_array[j]) > abs(A_array[i] - B_array[j+1]) and j+1 == m-1:
          
          C_array.append(B_array[j+1])      
    print(sum(C_array))

풀이

import sys

t = int(sys.stdin.readline())
# 이진탐색 함수 
def binary(i,B,start,end):
  diff = end - start
  if diff <= 1:
    return start
  mid = (start + end) // 2
  if i < B[mid]:
    return binary(i,B,start,mid)
  else:
    return binary(i,B,mid,end)

# 차이가 가장 작은 값의 인덱스를 반환
def findMin(c):
  curr = c[2]
  idx = 2
  if c[1] <= curr:
    curr = c[1]
    idx = 1
  if c[0] <= curr:
    curr = c[0]
    idx = 0
  return idx
 
for _ in range(t):
  # A의 총 개수 = n
  # B의 총 개수 = m
  n, m = map(int, sys.stdin.readline().split())
  A = list(map(int, sys.stdin.readline().split()))
  B = list(map(int, sys.stdin.readline().split()))
  B.sort()
  
  result = 0
  for i in A:
    p = binary(i,B,0,m)
    # p의 바로 앞, p, p의 바로 뒤 값
    diff = []
    diff.append(abs(B[p-1] - i))
    # A의 i값과 B배열에서 가장 가까운 값
    diff.append(abs(B[p] - i))
    diff.append(abs(B[(p+1) % m] - i))
    # 차이가 가장 작은 값의 인덱스
    idx = findMin(diff)
    result += B[p + idx - 1]
  print(result)

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