글 읽기 - 두 로직 간의 차이가 뭔가요? (하나는 시간초과)

jjy5349 1년 전 0

해당 문제에서 이진탐색을 통해서 문제를 해결하는데 처음에 1번으로 아무리 답을 제출해도 시간초과 오류가 났습니다.

그래서 구글링하다가 아무리봐도 문제가 없는데 계속 시간초과가 나서 참고한 블로그처럼 이진탐색 부분을 메소드로 빼버렸더니(2번) 통과를 했습니다.

왜 이런 건지 도저히 이해가 안되서 혹시 가르쳐주실 수 있으신가요?

# 1
import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
stack = [arr[0]]

for i in range(1, len(arr)):
    if stack[-1] < arr[i]:
        stack.append(arr[i])
    else:
        start = 0
        end = len(stack) - 1
        while start <= end:
            mid = (start + end) // 2
            if stack[mid] == arr[i]:
                start = mid
                break
            if stack[mid] < arr[i]:
                start = mid + 1
            else:
                end = mid - 1
        stack[start] = arr[i]

print(len(stack))

# ---------------------------------------------------------------------

#2
import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
stack = [arr[0]]

def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if stack[mid] == target:
            return mid
        elif stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

for i in range(1, len(arr)):
    if stack[-1] < arr[i]:
        stack.append(arr[i])
    else:
        stack[binary_search(arr[i], 0, len(stack) - 1)] = arr[i]

print(len(stack))

wnwoghd22 1년 전 1

완전히 동일한 로직에 대해 시간초과가 난다면 생각해볼 수 있는 건 변수 테이블 참조 문제인데요...

모든 언어가 비슷하지만, 변수 대입이나 참조 등의 구문을 만나게 되면 프로그램은 스택에서 지역 변수부터 찾기 시작해서 이름이 없으면 점차 밖으로 나가게 됩니다.

#1번은 변수 테이블이 4층으로 되어있고 #2번은 3층으로 되어있는 게 차이라면 차이겠네요.

설마 참조 시간의 차이가 정답 유무를 가를 수 있는지는 사실 저도 잘 모르겠습니다.

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

문제

문제

출처

ICPC

두 로직 간의 차이가 뭔가요? (하나는 시간초과)

jjy5349 1년 전 0

wnwoghd22 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말