[Python] 백준, 10816(이진 탐색)

분명 이진 탐색 알고리즘에 속해있는 문항이지만 이진 탐색으로 푸는 게 가장 비효율적인 것 같다... 방법도 잘 모르겠고.

 

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

10816번: 숫자 카드 2

 

 

여러번 수정을 거친 후의 난잡한 코드.

pop()함수를 이용해 리스트(seq)를 계속 갱신하며 이진 탐색으로 answer의 값을 증가시켜주려 했으나... index상의 문제와 복잡도로 인해 결국 답이 안 보여 구글링으로 다른 답을 확인했다.

​

그래도 collections모듈의 Counter함수를 배운것에 의의를 두자.

 

 

# PYTHON CODE (1) - 1차 시도

import sys
 
n = int(sys.stdin.readline())
list1 = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))
 
 
def binary_search(seq: list, key: int):
    pl, pr = 0, n - 1
    answer = 0
 
    while pl <= pr:
        pc = (pl + pr) // 2
 
        if seq[pc] == key:
            answer += 1
 
        elif seq[pc] > key:
            pr = pc - 1
 
        else:
            pl = pc + 1
 
    return answer
 
for i in list2:
    k = binary_search(list1, i)
    if k:

java의 경우에는 따로 주어져있지만, python은 따로 주어져 있지 않아 직접 구현을 해야한다. 구현 자체는 이진 탐색의 응용으로 충분히 할만 하다.

 

collections의 Counter모듈이랑 크게 쓰임새가 다르지 않지만 이진 탐색을 공부하는 김에 알아두면 좋을 것 같다.

 

 

 

# PYTHON CODE (2) - BinarySearch(LowerBound, UpperBound)

from typing import Any
 
def upperbound(pl, pr, key, seq: list):
    while pl < pr:
        pc = (pl + pr) // 2
        if seq[pc] <= key:
            pl = pc + 1
        else:
            pr = pc
 
    return pr
 
def lowerbound(pl, pr, key, seq: list):
    while pl < pr:
        pc = (pl + pr) // 2
        if seq[pc] < key:
            pl = pc + 1
        else:
            pr = pc
 
    return pr

 

 

# PYTHON CODE (3) - dictionary 매소드와 Counter

from collections import Counter
import sys
 
n = int(sys.stdin.readline())
list1 = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))
 
dic1 = Counter(list1)
 
print(' '.join(str(dic1[x]) if x in dic1 else '0' for x in list2))