99클럽(3기) - 코테스터디 6일차 TIL # 이분탐색

프로그래머스 - 18016. 숫자 카드 2

1. 문제 설명

 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 포함 개수를, 아니면 0을 공백으로 구분해 출력한다. 어제 문제는 상근이가 가지고 있는 숫자 카드 N개에 M개의 수 중에 하나라도 포함되어 있으면 1을 반환했다면, 오늘 문제는 포함 개수를 구해야 한다. 

첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 

 

2.  제한 사항

• 1 <= N <= 500,000
• 1 <= M <= 500,000
• 10,000,000 <= 숫자 카드에 적혀있는 수 <= 10,000,000

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이 (시간초과)

ns.count(val)의 시간복잡도가 O(N)이기 때문에 for문의 최종 시간복잡도는 O(N*M)이 되었고, 시간초과가 발생했다. count()에 대한 최적화를 해야한다. 

import bisect

N = int(input())
ns = sorted(map(int, input().split()))
M = int(input())
ms = map(int, input().split())

for val in ms:
    index = bisect.bisect_left(ns, val)
    if index < N and ns[index] == val:
        print(ns.count(val), end = " ")
    else:
        print(0, end = " ")

 

 

5. 두 번째 풀이

bisect.bisect()를 사용해 val의 가장 오른쪽 인덱스 + 1값을 구하고, 앞서 bisect.bisect_left()로 구한 가장 왼쪽 인덱스를 빼서 개수를 구했다.   

import bisect

N = int(input())
ns = sorted(map(int, input().split()))
M = int(input())
ms = map(int, input().split())

for val in ms:
    left_idx = bisect.bisect_left(ns, val)
    if left_idx < N and ns[left_idx] == val:
        right_idx = bisect.bisect(ns, val) 
        print(right_idx - left_idx, end = " ")
    else:
        print(0, end = " ")

 

 

6. 느낀점

어제 bisect 사용법을 정리했는데, bisect.bisect()를 개수 계산에 사용하지 못 했다. 아주 간단한 아이디어였는데! 아쉽다.