[Algo Rhythm🕺💃] 프로그래머스 - 숫자 게임

💫문제 분석

A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열을 $A$, i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열을 $B$라고 하자.

 

이때 두 배열의 원소 $a_i, b_i$, 배열의 크기 $L$은 아래와 같이 정의할 수 있다.

$1 \le L = \left\vert A \right\vert = \left\vert B \right\vert \le 10^5$

$1 \le a_i, b_i \le 10^9 (a_i \in A, b_i \in B, i \in \left[ 1, L \right])$

 

A팀은 출전 순서가 이미 고정되어 있다. 따라서 B팀이 최대 승점을 얻기 위해서는 각 $a_i$를 패배할 수 있는 즉, $a_i < b_i$ 조건을 만족하는 가장 작은 $b_i$와 매칭하면 된다.

 

🔥문제 풀이

앞서 분석에서 언급했듯이 우리는 각 $a_i$를 $a_i \lt b_i$를 만족하는 가장 작은 $b_i$와 매칭해야 한다.

가장 간단하게 모든 $b_i$를 일일이 살펴보는 방법도 가능하다. 하지만 $B$를 정렬한 뒤 binary search를 이용하면 더 빠르게 매칭할 수 있다.

 

정리하면 이 문제는 다음과 같은 알고리즘으로 해결가능하다.

1. $B$를 오름차순으로 정렬
2. 모든 $a_i$에 대하여 다음 과정 실행
   1. binary search를 통해 $a_i \lt b_i$를 만족하는 가장 작은 $b_i$ 찾기
   2. 찾으면 승점에 1점을 추가하고 해당 $b_i$를 다음 과정에서 제외

 

✨복잡도 분석

두 배열 $A, B$의 크기를 $n$이라고 하자.

⏰시간 복잡도 : $O(n\log n)$

• $B$ 정렬 : $O(n \log n)$
• 모든 $a_i$에 대하여 binary search로 $a_i \lt b_i$를 만족하는 가장 작은 $b_i$ 찾기 : $O(n \log n)$

🏠공간 복잡도 : $O(n)$

 

🌈코드

	def lower_bound(arr, target):
	left = 0
	right = len(arr)
	while(left < right):
	mid = (left + right) // 2
	if target < arr[mid]:
	right = mid
	else:
	left = mid + 1
	return left
	def solution(A, B):
	answer = 0
	B.sort()
	for a in A:
	lb = lower_bound(B, a)
	if len(B) > lb:
	answer += 1
	del B[lb]
	return answer

view raw programmers_number_game.py hosted with ❤ by GitHub

 

🌏문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12987