문제 바로가기
정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다.
문제:
A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있는 값 중 A[i] 에 가장 가까운 값 (절대값 차이가 가장 작은 값)으로 정의 된다. 만약 이 조건을 만족하는 값들이 여럿 있는 경우, 그 중 가장 크기가 작은 값으로 정의 된다.
예를 들어 A = [20, 5, 14, 9] 그리고 B = [16, 8, 12] 라고 해보자.
- C[1] = 16 이다 - 왜냐하면 B[1] = 16이 A[1] = 20에 가장 가깝기 때문이다.
- C[2] = 8 이다 - 왜냐하면 B[2] = 8이 A[2] = 5에 가장 가깝기 때문이다.
- C[3] = 12 이다 - 왜냐하면 B[1] = 16 와 B[3] = 12 모두 A[3] = 14에 가장 가깝지만, B[3]의 값이 더 작기 때문이다.
- C[4] = 8이다.
이 예제의 경우 C = [16, 8, 12, 8]으로 정의된다. 두 배열 A와 B가 주어졌을 때, 새로운 배열 C를 계산하여 배열 C에 포함된 값들의 합을 구하는 프로그램을 작성하시오.
입력:
첫 줄에 테스트 케이스의 수 T (1 <= T <= 10)가 주어진다. 각 테스트 케이스는 세 줄에 걸쳐서 주어진다. 첫 줄에는 n과 m이 공백으로 구분되어 주어진다 (1 <= n, m <= 10^6). 두 번째 줄에는 공백으로 구분된 n개의 정수가 주어지며, A[1] 부터 A[n]을 나타낸다 (각각의 값은 1이상 10^9 이하이다). 세 번째 줄에는 공백으로 구분된 m개의 정수가 주어지며, B[1] 부터 B[m]을 나타낸다 (각각의 값은 1이상 10^9 이하이다). 앞서 언급한대로, A와 B는 각각 서로 다른 양의 정수들을 포함한 배열들이다.
출력:
각 테스트 케이스에 대해 배열 C를 구하고 해당 배열의 모든 원소 합을 한 줄에 출력하시오.
풀이:
import sys
t = int(input())
for _ in range(t):
n, m = map(int,sys.stdin.readline().split(" "))
list_A = list(map(int,sys.stdin.readline().split(" ")))
list_B = sorted(list(map(int,sys.stdin.readline().split(" "))))
count = 0
# A 에 가까운 수열
res = []
for num in list_A:
left = 0; right = m - 1
while left < right:
mid = (left + right) // 2
if list_B[mid] <= num: # 타겟 넘버보다 작으면 왼쪽 올려줌
left = mid + 1
else:
right = mid
if left == 0 :
# 그 위치가 0 이면
count += list_B[0]
else:
# 아닐때 앞에 꺼 보다 큰 값인지 비교해줘야함
count += list_B[left] if num - list_B[left-1] > list_B[left] - num else list_B[left-1]
break
# A = 5 9 14 20
# B = 8 12 16
그냥 이중 포문으로 하면 n,m 이 너무 많아서 무조건 시간초과 난다.
이분탐색으로 target 숫자보다 한 단계 큰 숫자를 구해주고, 타겟넘버랑 left, left -1 에 차이중에 차이가 적은 것으로 한다.
차이가 같으면 작은값으로 한다.
댓글