【경쟁 프로 전형적인 90문】007의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

이슈007-CP클래스

문제 개요

배열 A 중에서 각 B에 가장 가까운 값을 찾아 그 절대 값을 출력합니다.

해결 방법

우선, 모든 A, B의 조합에 있어서, 차례로 절대치를 구해 가는 방법을 생각할 수 있을까 생각합니다.
그러나, 이 생각에서는 계산량이 NQ가 되고, N, Q는 각각 $10^5$주문이기 때문에, TLE가 됩니다.

그래서 이번에는 사전에 A를 정렬하고 이분 탐색을 수행하여 B에 가장 가까운 값을 고속으로 구합니다.
이 때의 계산량은, 소트시에 걸리는 계산량이 $NlogN$, B에 가까운 값의 이분 탐색에 $logN$, 그 계산을 Q회 실시하므로, 합계의 계산량은 $(N+Q) logN$가 되고, 이것은 시간내에 충분히 시간이 걸립니다.
※이분 탐색에 관해서는 여기 를 참고해 주십시오.

구현의 흐름은 다음과 같습니다.
1. A를 정렬합니다.
2. B에 가까운 값을 이분 탐색으로 구하여 절대값을 계산, 출력한다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

# Aをソート
A.sort()

# 出力する答えを配列で格納
ans = []


for i in range(Q):
  b = int(input())

# b以下を満たす範囲をleft, bより大きい範囲をrightとする
  left = -1
  right = N

  while right - left > 1:
    mid = (right + left)//2
    if A[mid] <= b:
      left = mid
    else:
      right = mid

# B以下を満たす値とBより大きい値で、絶対値を比較する。
# leftの境界値を含まないようifで条件分岐
  comp1 = 10**9
  comp2 = 10**9
  if left >= 0:
    comp1 = abs(A[left]-b)
  if left < N-1:
    comp2 = abs(A[left+1]-b)
  ans.append(min(comp1, comp2))

# 答えを出力
for i in range(Q):
  print(ans[i])

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.
또, 이 기사를 읽고 이해할 수 있었던 분은 꼭 LGTM를 눌러 주실 수 있으면 기쁩니다.
(기사 투고의 모티베가 됩니다.)

여기까지 읽어 주셔서 감사합니다.