[백준-python] 10816 숫자 카드 2

첫 번째 시도

while문으로 일치하는 숫자가 있으면 해당 target을 리스트에서 remove한 뒤 다시 이진 탐색 하게 해봤더니 시간 초과가 났다.

#coding:utf8
# 숫자 카드2
# 이진 탐색

from sys import stdin

M = int(stdin.readline())
MList = sorted(map(int, stdin.readline().split()))
N = int(stdin.readline())
NCards =map(int, stdin.readline().split())

def binary_search(searchList, target, startIndex, endIndex):
    if startIndex > endIndex:
        return False

    mid = (startIndex + endIndex) // 2
    if searchList[mid] == target:
        return True
    if target > searchList[mid]:
        return binary_search(searchList, target, mid+1, endIndex)
    else:
        return binary_search(searchList, target, startIndex, mid-1)

result = list()
for n in NCards:
    count = 0
    startIndex = 0
    while True:
        endIndex = len(MList) -1
        if binary_search(MList, n, startIndex, endIndex):
            count += 1
            MList.remove(n)
        else:
            break
    result.append(count)
print(" ".join(map(str, result)))

두 번째 시도

일치하는 게 없을 때까지 반복해서 이진탐색하는 방식은 시간초과였다.
그래서 한 번 탐색할 때 인접한 숫자들까지 검사하는 식으로 해봤지만 출력초과다.
어차피 작동도 안되는 코드..
뭔가 접근 방식 자체가 잘못된 것 같았다.

#coding:utf8
# 숫자 카드2
# 이진 탐색

from sys import stdin

M = int(stdin.readline())
MList = sorted(map(int, stdin.readline().split()))
N = int(stdin.readline())
NCards =map(int, stdin.readline().split())
count = 0


def binary_search(searchList, target, startIndex, endIndex):
    print(searchList, target, startIndex, endIndex)
    global count
    if startIndex > endIndex:
        return False

    mid = (startIndex + endIndex) // 2

    if searchList[mid] == target:
        count += 1
        near = mid
        left = True
        right = False
        while near >= startIndex and near <= endIndex:
            if searchList[near] == target:
                if near != mid:
                    count += 1
            else:
                if left:
                    left = False
                    right = True
                if right:
                    right = False
                near = mid
                continue

            if left:
                near -= 1
            elif right:
                near += 1
            else:
                break
        return True

    if target > searchList[mid]:
        return binary_search(searchList, target, mid+1, endIndex)
    else:
        return binary_search(searchList, target, startIndex, mid-1)

result = list()
for n in NCards:
    count = 0
    startIndex = 0
    endIndex = len(MList) -1
    binary_search(MList, n, startIndex, endIndex)
    print(count)
    result.append(count)
print(" ".join(map(str, result)))

최종 정답

결국 다른 사람 코드를 봤는데 해쉬테이블 자료구조(python에서는 딕셔너리)를 이용해서 해결하셨다.
알고리즘 분류를 한번 볼걸 그랬군

from sys import stdin
_ = stdin.readline()
N = map(int,stdin.readline().split())
_ = stdin.readline()
M = map(int,stdin.readline().split())
hashmap = {}
for n in N:
    if n in hashmap:
        hashmap[n] += 1
    else:
        hashmap[n] = 1

print(' '.join(str(hashmap[m]) if m in hashmap else '0' for m in M))

Reference

• https://chancoding.tistory.com/45