글 읽기 - 시간초과 조언 부탁드립니다

ljm3749 1년 전 0

줄일 수 있는 부분이 있을까요?

다시 작성하는게 더 나을지 모르겠습니다

import sys

input = sys.stdin.readline

N = int(input())

num_lst = list(map(int, input().split()))

M = int(input())

num_lst2 = list(map(int, input().split()))

num_lst = sorted(num_lst)


def BS(i, num_lst, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2

    cnt = 0

    if i > num_lst[mid]:
        return BS(i, num_lst, mid + 1, end)

    elif i < num_lst[mid]:
        return BS(i, num_lst, start, mid - 1)

    elif i == num_lst[mid]:
        for j in range(start, end+1):

            if i == num_lst[j]:
                cnt += 1

    return cnt


result = []

for i in num_lst2:
    start = 0
    end = N - 1
    result.append(BS(i, num_lst, start, end))

for i in result:
    print(i,end=" ")

djm03178 1년 전 1

수가 같을 때 반복문을 돌려 같은 수들을 세면 이분 탐색을 하는 의미가 없습니다. 모든 수가 전부 같고, 그 수만 계속해서 찾는다면 시간이 얼마나 걸리게 될까요?

hkhkhk5452 1년 전 1

BS(binary search)가 O(log(n)) 만에 cnt를 찾아야 O(m*log(n)) 되서 1초 안에 풀수 있습니다.

지금 31~34 라인을 보면 O(n) 만에 cnt를 찾고 있습니다. 이렇게되면 O(m*n)이되어서 1초안에 풀 수 없습니다. (50만*50만 = 2500억 > 10억 = 1초)

따라서 미리 입력을 받을때 같은 숫자가 들어오면 해당 숫자를 cnt하는 변수를 만드는 식으로 접근하면 해결하실 수 있을겁니다.

key : value의 dictionary 형식으로 하면 될것같네요

10(입력 숫자):1(갯수)

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

문제

문제

출처

ICPC

시간초과 조언 부탁드립니다

ljm3749 1년 전 0

djm03178 1년 전 1

hkhkhk5452 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말