글 읽기 - 10815 숫자카드 파이썬 걸린시간 관련 질문있습니다.

sthsdfg 1년 전 0

문제 알고리즘 분류에 이분탐색이 있어서 이분탐색 함수를 짜서 사용했는데, 다른 정답들을 보니 그냥 in 으로 탐색을 한 함수가 훨씬 빠르더라구요?

그래서 이러면 그냥 함수가 아닌 단순 for문으로 해도 되지 않을까 했는데 그건 시간초과가 났습니다.

어떤 차이가 있는 건지 궁금합니다.

#제 코드
import sys
def Incards(cards,nums):

    cards.sort()
    result = []
    
    for num in nums:
        start = 0
        end = len(cards) - 1
        while True:
            if start > end:
                result.append(0)
                break
            mid = (start+end)//2
            if cards[mid] == num:
                result.append(1)
                break
            elif cards[mid] < num:
                start = mid + 1
            elif cards[mid]:
                end = mid - 1        
    
    return result
    
n = int(sys.stdin.readline())
cards = list(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())
nums = list(map(int,sys.stdin.readline().split()))

result = Incards(cards,nums)
print(*result,end=' ')

#다른 분 코드
import sys

def test():
    input()
    b = set(input().split())
    input()
    d = input().split()
    res = ''
    for i in d:
        if i in b:
            res += '1 '
        else:
            res += '0 '
    print(res)

test()

#시간초과 난 코드
import sys
    
n = int(sys.stdin.readline())
cards = sorted(list(map(int,sys.stdin.readline().split())))
m = int(sys.stdin.readline())
nums = sorted(list(map(int,sys.stdin.readline().split())))

for num in nums:
    if num in cards:
        print(1, end=' ')
    else:
        print(0, end=' ')

djm03178 1년 전 1

list에서의 in은 리스트의 원소를 하나씩 전부 비교해가면서 찾기 때문에 매우 느립니다. 평균적으로 리스트의 길이에 비례하는 시간이 걸립니다.

반면 set은 해시를 사용하기 때문에 평균 상수 시간에 원소를 찾을 수 있습니다.

sthsdfg 1년 전 0

list와 set의 차이가있었군요! 감사합니다!!

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

문제

문제

출처

ICPC

10815 숫자카드 파이썬 걸린시간 관련 질문있습니다.

sthsdfg 1년 전 0

djm03178 1년 전 1

sthsdfg 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말