글 읽기 - 20551번 sort마스터 질문있습니다!

konkuk_fly 3년 전 0

문제는 '시간 초과'입니다

공지에 읽어보니 리스트 사용으로 인해 시간복잡도가 커지는걸로 예상됩니다

제 생각에는 이중 for문에서 리스트 비교할때 시간이 오래걸리는거 같습니다

혹시 맞다면 저 부분의 코드를 깔끔하게 수정할 수 있을만한 힌트나 답을 주신다면 감사하겠습니다

문제는 q_element 배열에 있는 값과 element 배열의 값을 비교해서

q_element 에 있는 값이 element 에 있다면 해당 element(정렬된) index 값을 출력하고

없으면 -1 을 출력합니다

vscode에서는 예제 2개 다 잘 돌아갑니다만

백준내에서 시간초과를 어떻게 해결할수 있을지 모르겠습니다,, 도와주세요!

import sys
e_cnt, q_cnt = map(int, sys.stdin.readline().split(' '))

element = []
for i in range(0, e_cnt):
    element.append(int(sys.stdin.readline()))

q_element = []
for i in range(0, q_cnt):
    q_element.append(int(sys.stdin.readline()))

element  = sorted(element)

for i in range(0, q_cnt):
    none = 0
    for j in range(0, e_cnt):
        if q_element[i] == element[j]:
            print(j)
            break
        else:
            none += 1
            if none == 5:
                print(-1)

39dll 3년 전 1

이 문제는 이분 탐색으로 풀어야 합니다.

이분 탐색을 공부하신 뒤, https://www.acmicpc.net/proble...를 먼저 풀어보시는 걸 추천드립니다.

konkuk_fly 3년 전 0

답변 감사드립니다~

빠른 시간내에 풀어보겠습니다!!

konkuk_fly 3년 전 0

선생님 이분탐색으로 풀어봤는데도 불구하고

'시간초과'가 납니다

어째서일까요?ㅠㅠ

혹시 한수 가르침을 주실수 있을지 질문 올려봅니다!

from sys import stdin, stdout
e_cnt, q_cnt = map(int, stdin.readline().split(' '))

element = []
for i in range(0, e_cnt):
    element.append(int(stdin.readline()))
element  = sorted(element)

q_element = []
for i in range(0, q_cnt):
    q_element.append(int(stdin.readline()))

print(element)
print(q_element)

def binary(l, element, start, end):
    if start > end:
        return -1
    if element.count(l) == 0:
        return -1
    m = (start+end)//2

    if l == element[m]:
        while element[m] == element[m-1]:
            m -= 1
        return m
    elif l < element[m]:
        return binary(l, element, start, m-1)
    else:
        return binary(l, element, m+1, end)

for l in q_element:
    start = 0
    end = len(element)-1
    print(binary(l, element, start, end))

39dll 3년 전 1

각 쿼리마다 binary 함수가 logN번 실행되는데, count 함수의 시간 복잡도는 O(N)입니다. 따라서 binary 함수의 시간 복잡도는 O(logN)이 아니고 O(NlogN)이라서 상당히 느립니다. count 함수를 사용하지 않아야 합니다.

두 번째 문제로, 만약 배열이 모두 같은 수로 이루어질 경우, 24번째 while문에서 무한루프가 일어납니다. 저렇게 1씩 빼면 안 되고, lower_bound라는 것을 공부하신 뒤 다시 풀어보시는 것을 추천드립니다.

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

문제

문제

출처

ICPC

20551번 sort마스터 질문있습니다!

konkuk_fly 3년 전 0

39dll 3년 전 1

konkuk_fly 3년 전 0

konkuk_fly 3년 전 0

39dll 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말