공부하는허딩크 : https://www.youtube.com/live/NQxG_GQn54s?feature=shared
이진탐색의 기본형태를 몇 문제 풀고 나서 해당 문제를 풀었다.
<첫번째 시도 : 맞았습니다>
일단, 이진탐색으로 해결은 했는데 기존에는 어떤 특정 요소를 찾는 것이었다면 이번에는 목표값보다 큰 수를 찾는 것이라서 어떤 조건으로 if를 해야하는지 return을 해야하는지 많이 고민했다.
※B_nums를 한개씩 꺼내서 A_nums를 이진탐색해서 B_nums보다 큰 값들을 구하는 목적이다.
※ 예시 실행할 때 아래와 같이 된다. 즉, start는 m보다 큰 값들이 시작되는 인덱스를 가리킨다.
i = 3일때
start 0, end 4 일때
1. mid = 2 arr[2] = 3, i = 3과 같아서 else로 가서 start = 3
start 3, end 4 일때
2. mid = 3 arr[3] = 7, i = 3 if로 가서 end = 2 while탈출
return len(arr) = 5 - 3 = 2
i = 6일때
1. mid = 2 arr[2] = 3, i = 6 else로 가서 start = 3
start 3, end 4 일때
2. mid = 3 arr[3] = 7, i = 6 if로 가서 end = 2 while탈출
return len(arr) = 5 - 3 = 2
i = 1일때
1. mid = 2 arr[2] = 3, i = 1 else로 가서 end = 1
start 0, end 1 일때
2. mid = 0 arr[0] = 1, i = 1 else로 가서 start = 1
start 1, end 1 일때
3. mid = 1 arr[1] = 1, i = 1 else로 가서 start = 2 while탈출
return len(arr) = 5 - 2 = 3
import sys
input = sys.stdin.readline
T = int(input())
#Binary Search
def BS(arr, m):
start, end = 0, len(arr) - 1
while start <= end: #이진검색 기본형
mid = (start + end) // 2
if arr[mid] > m:
end = mid - 1
else:
start = mid + 1
#이때 start는 배열에서 m보다 큰 값들이 시작되는 인덱스를 가리킨다.
return len(arr) - start
for _ in range(T):
A, B = map(int, input().split())
A_nums = list(map(int, input().split()))
B_nums = list(map(int, input().split())) #[3, 6, 1]
A_nums.sort() #[1, 1, 3, 7, 8]
cnt = 0
for i in B_nums:
cnt += BS(A_nums, i)
print(cnt)
"""
i = 3일때
start 0, end 4 일때
1. mid = 2 arr[2] = 3, i = 3과 같아서 else로 가서 start = 3
start 3, end 4 일때
2. mid = 3 arr[3] = 7, i = 3 if로 가서 end = 2 while탈출
return len(arr) = 5 - 3 = 2
i = 6일때
1. mid = 2 arr[2] = 3, i = 6 else로 가서 start = 3
start 3, end 4 일때
2. mid = 3 arr[3] = 7, i = 6 if로 가서 end = 2 while탈출
return len(arr) = 5 - 3 = 2
i = 1일때
1. mid = 2 arr[2] = 3, i = 1 else로 가서 end = 1
start 0, end 1 일때
2. mid = 0 arr[0] = 1, i = 1 else로 가서 start = 1
start 1, end 1 일때
3. mid = 1 arr[1] = 1, i = 1 else로 가서 start = 2 while탈출
return len(arr) = 5 - 2 = 3
"""
<두번째 시도 : 맞았습니다.>
재귀함수를 활용해서 해결했다.
아직까지 조금 헷갈린다. 더 많이 연습해야 겠다.
import sys
input = sys.stdin.readline
T = int(input())
def BS(m, start, end):
if start > end:
return A - start
mid = (start + end) // 2
if A_nums[mid] > m:
end = mid - 1
else:
start = mid + 1
return BS(m, start, end)
for _ in range(T):
A, B = map(int, input().split())
A_nums = list(map(int, input().split()))
B_nums = list(map(int, input().split())) #[3, 6, 1]
A_nums.sort() #[1, 1, 3, 7, 8]
cnt = 0
for i in B_nums:
cnt += BS(i, 0, len(A_nums) - 1)
print(cnt)
<다른사람 풀이 참고 : 이진탐색활용하지 않고 구현으로 해결>
첫번째 시도는 시간초과가 나왔다. (이중for문이 문제인 것 같다.)
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
A, B = map(int, input().split())
A_nums = list(map(int, input().split()))
B_nums = list(map(int, input().split())) #[3, 6, 1]
cnt = 0
for a in A_nums:
for b in B_nums:
if b < a:
cnt += 1
print(cnt)
※투포인터 알고리즘을 사용해야 하나??? 아래 내용 투포인터 복습 한 이후에 다시 리뷰 필요
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
index = 0
answer = 0
cnt = 0
for i in range(n):
while True:
if index == m or a[i] <= b[index]:
answer += index
break
else:
index += 1
print(answer)