[Python] BOJ(백준) 20551번 - Sort 마스터 배지훈의 후계자

1. 링크

https://www.acmicpc.net/problem/20551

2. 난이도(solved.ac 참고)

실버4

3. 풀이

	# https://www.acmicpc.net/problem/20551
	def lower_bound(nums, target):
	left, right = 0, len(nums)-1
	while left <= right:
	mid = (left + right) // 2
	if nums[mid] < target:
	left = mid + 1
	elif nums[mid] > target:
	right = mid - 1
	elif nums[mid] == target:
	if right == mid:
	break
	right = mid
	if nums[mid] == target:
	return mid
	else:
	return -1
	import sys
	input = sys.stdin.readline
	n, m = map(int, input().split())
	a = sorted([int(input()) for _ in range(n)])
	for i in range(m):
	z = int(input())
	print(lower_bound(a, z))

view raw BOJ20551.py hosted with ❤ by GitHub

실버4라 만만하게 봤는데 생각보다 시행착오를 많이 겪었던 문제였다.

 

일단 이분 탐색을 사용해야 되는 문제였는데, 거기서도 lower_bound라는 개념을 익힐 수 있는 문제였다. lower_bound란 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 이분탐색에서 살짝만 바꿔주면 된다. 물론 당연히 이분탐색의 전제와 같이 sort가 되어있어야 한다.

 

mid를 가운데 값으로 설정하고 target보다 작으면 mid+1로 왼쪽 범위 날리고, target보다 크면 right = mid - 1로 오른쪽 범위 날리고, 같을 경우가 문제다.

[-1, 1, 3, 3, 3, 4, 5, 6, 6]

이런 배열이 있다고 해보자. 3이라는 값을 lower_bound 함수를 돌렸을 경우 구해야 할 답은 2이다. 왜냐면 3이 가장 먼저 나타난 인덱스가 2이기 때문이다.

이분 탐색에서는 mid값이 3(target)이 되면 그대로 그 인덱스를 반환하고 끝마치는데, 여기서는 같을 경우 right = mid를 계속 해줌으로써 while문에서 벗어날 때까지 right의 값을 하나씩 줄여준다. 이렇게 해서 결국 그 target과 같은 값이 가장 먼저 등장하는 인덱스를 찾을 수 있게 되는 것이다.