글 읽기 - 파이썬 반례좀 부탁드립니다 ㅠㅠ

dlehrud451 2년 전 0

제목에서 처럼 반례좀 부탁드립니다. 이진 탐색으로 같은 수가 존재할 경우 그 수를 dfs로 구하여 프린트 하도록 프로그램을 작성하였는데 틀린부분이 어디인지 모르겠습니다.

import sys
from collections import deque
input=sys.stdin.readline

#이진탐색
def check(start,end,target):
    while start<=end:
        mid=(start+end)//2
        if narray[mid]==target:
            return mid
        elif narray[mid]>target:
            end=mid-1
        elif narray[mid]<target:
            start=mid+1
    return -1

#몇개인지 구하기 위해 dfs
def bfs(idx,count):
    q=deque()
    q.append((idx,count))
    visit.add(idx)
    while q:
        idx,count=q.popleft()
        for i in range(2):
            nidx=idx+di[i]
            if 0<=nidx<len(narray):
                if narray[idx]==narray[nidx] and nidx not in visit:
                    visit.add(nidx)
                    q.append((nidx,count+1))
    visit.clear()#중복이 가능하므로 set clear
    return count



n=int(input())
narray=list(map(int,input().split()))
m=int(input())
marray=list(map(int,input().split()))
narray.sort()

di=[1,-1]
visit=set()#dfs에서 idx 방문처리 위한 set
for i in marray:
    idx=check(0,len(narray)-1,i)
    if idx==-1:
        print(0,end=' ')
    else:
        print(bfs(idx,1),end=' ')

ai4youej 2년 전 1

반례입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 반례좀 부탁드립니다 ㅠㅠ

dlehrud451 2년 전 0

ai4youej 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말