백준-10816 숫자카드 2

문제 😀

---

BS를 이용해서 풀려했는데 시간초과로 풀수가 없었다.
그래서 풀이법을 찾는중 lower bound와 upper bound의 개념을 찾게되었다.

개념 😃

---

lower bound는 타겟인 수보다 크거나 같은 최초 위치를 찾아내고
upper bound는 타겟인 수보다 초과인 최초 위치를 찾아낸다.

물론 lower bound와 upper bound도 BS와 같이 데이터가 정렬이 되어있어야한다.

1 2 2 4 5 5 5 8 10 의 수열이 있다고 하자. 이중에서 target이 5의 lower bound와 upper bound를 찾아보자

1. lower bound

• 1 2 2 4 5 5 5 8 10 , 앞에서부터 5번째 있는(리스트라고 생각하면 인덱스가 4인)이 5가 lower bound의 값이다.

2. upper bound

• 1 2 2 4 5 5 5 8 10, 앞에서부터 8번째에 있는, 리스트라고 생각하면 인덱스가 7인 8이 upper bound의 값이다.

lower bound와 upper bound는 Binary Search를 살짝 응용해서 구현할수 있다.

BS는 어떠한 target을 찾아낸뒤 return을 해도 무방한 알고리즘이지만 lowerbound와 upperbound는 start < end가 되기 직전까지 무조건 순회해야한다.(난 반복문으로 풀었다.)

코드를 보면서 BS와의 차이를 확인해보자

코드 😁

---

import sys

N = int(sys.stdin.readline().rstrip())
cards = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().rstrip().split()))

cards.sort()

def upper_bound(start, end, target):
  while start < end:
    mid = (start + end) // 2
    if target >= cards[mid]:
      start = mid + 1
    else:
      end = mid
  
  return end + 1

def lowr_bound(start, end, target):
  while start < end:
    mid = (start + end) // 2
    if target > cards[mid]:
      start = mid + 1
    else:
      end = mid
    
  return end + 1
for num in nums:
  print(upper_bound(0, len(cards), num) - lowr_bound(0, len(cards), num), end=' ')

upper_bound와 lower_bound의 차이를 보면 if target > cards[mid]:와 if target >= cards[mid]:부분이 차이가 있는걸 볼 수가 있다. upper_bound는 target과 cards[mid]가 같아도 start = mid + 1로 계속 위치를 조정하는 것을 볼 수가 있다. 이를 통해서 target보다 초과하는 첫번째 인덱스를 구할수 있다.

이 문제에서 틀렸던 부분은 end의 인자로 전달하는 값때문에 좀 틀렸다.

end로 전달하는 값을 len(cards) - 1이 아닌 len(cards)로 전달해야 적절한 값을 도출할수 있다, 왜냐면 upper_bound와 lower_bound에서 end + 1을 리턴하기 때문이다.

느낀점 🤣

---

1. lower_bound, upper_bound를 알게 되었다.
2. 두 개념을 구현하는데 머리로만 하려다가 직접 종이에 쓰면서 해보니 구현이 되었다. 무조건 쓰면서 하자.