글 읽기 - 이분 탐색 법 구현이 잘못된 걸 까요?

bomul1128 2년 전 0

대충 어떤 흐름으로 문제가 풀리는지는 이해했습니다만

나름대로 이분 탐색법을 구현해서 제출했는데 시간초과가 뜨네요

어떻게 고치면 될 지 고수님들께 여쭤봅니다..

# 12015 가장 긴 증가하는 수열 찾기

from sys import stdin as s
import math

def add_sort(sorted_list, new):
    if sorted_list[-1] < new:
        sorted_list.append(new)
    elif sorted_list[-1] > new: # 이분 탐색 구현?
        i = len(sorted_list) // 2
        n = i
        while True:
            if i == 0:
                break
            if sorted_list[i - 1] < new <= sorted_list[i]:
                break
            if sorted_list[i] > new:
                i = i - math.ceil(n / 2)
            elif sorted_list[i] < new:
                i = i + n // 2
            else:
                break
            n = n // 2
        sorted_list [i] = new
    return sorted_list



a = int( s.readline() )
num_list = list( map(int, s.readline().split() ) )

my_list = [num_list[0]]
for i in num_list[1:]:
    my_list = add_sort(my_list, i)
print(len(my_list))

bomul1128 2년 전 0

while 구문에 갇히는 경우가 있는 거였네요

질문 올리기 전에 더 확인해봤어야했는데..

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

문제

문제

출처

ICPC

이분 탐색 법 구현이 잘못된 걸 까요?

bomul1128 2년 전 0

bomul1128 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말