(파이썬)이분 탐색 - 숫자 카드 2

학교 알고리즘 소모임에서 세미나로 1주 간격으로 알고리즘/자료구조 세미나를 진행한다.

저번 주에 약속 때문에 못 들었는데, 오늘 '이분탐색' 영상을 찾아서 다시 봤다.

(오늘 주제는 우선순위 큐였음)

 

세미나는 백준 다이아.. 이상인 학우분들이 진행한다.

(빡고수 ㄷㄷ)

---

이분 탐색을 하는 가장 큰 조건!

 

'단조성이 있는 배열, 함수'

 

단조성은 우상향, 우하향, 오름차순, 내림차순과 같이 일정한 방향성을 띄는 성질을 얘기한다.

어떤 흐름(배열, 함수)에서 특정한 값을 탐색할 때 반으로 나눠서 탐색하는 것이다.

 

출처 : 알고리즘 소모임 유튜브 (비공개)

위 상황의 경우에는 특정 분기점(k)를 기준으로 true / false로 이어지는 단조성(우하향이라고 봐도 무방)을 갖는다.

이런 상황에서 좌/우 값을 좁혀가면서 찾는 것이 이분 탐색이다.

---

---

10816 - 숫자 카드 2

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

이 문제는 굳이 이분 탐색을 쓰지 않고도 풀 수 있지만, 이분 탐색을 이용해서 풀어보기로 했다.

 

<이분 탐색 안 쓴 풀이>

in 을 이용해서 배열을 확인 할 때, 선형으로 탐색하기 때문에 set을 이용하는 것이 빠르다고 한다.

실제로 set 안쓰고 배열 갖다 박아서 찾으면 시간 초과 뜸.

---

<이분 탐색을 이용한 풀이>

분기가 왜 빨갛지?

cards.sort()를 이용해서 단조성을 부여한다.

특정 중복 요소들을 카운트해서 dict로 만들어준다.

이분 탐색해서, 있다면 dict의 value 값(개수)를 프린트한다.

 

사실 위의 풀이보다 한참 느린데.. 적용해서 풀어봤다.

---

세미나에서 특정 문제들이 뿜는 풀이방법에 대한 냄새를 캐치하는 방법도 알려줬다.

지금 이분탐색의 경우에는 최대/최소값, 단조성 등이 그 힌트가 된다.

오늘 처음 풀어봤지만, 할만 해서 다행이었다.

나머지 문제들도 풀어봐야지.