글 읽기 - 11%에서 시간초과

alsrms27 3년 전 0

11%에서 시간초과가 뜹니다.,

어떤 반례가 있는지 모르겠습니다.,.

import sys
def find_max(max,possible):
	while True:
	    flag = True
	    num_list = list(map(int, list(str(max))))
	    for i in num_list:
	        if possible[i] == False:
	            flag = False
	            max += 1
	            break
	    if flag == True:
	        break
	return max
def find_min(min,possible):
	while True:
	    flag = True
	    num_list = list(map(int, list(str(min))))
	    for i in num_list:
	        if possible[i] == False:
	            flag = False
	            min -= 1
	            break
	    if min < 0:
	    	return
	    if flag == True:
	        break
	return min

num = int(sys.stdin.readline())
min_num = num
max_num = num
count_answer = 0
exclude_count = int(sys.stdin.readline())
if exclude_count == 0:
	count_answer = min(abs(100-num),len(num))
else:
	exclude_nums = list(map(int, sys.stdin.readline().rstrip().split()))
	if (num >= 98 and num <= 103) or exclude_count == 10:
		count_answer = abs(100-num)
	elif exclude_nums == list(range(1,10)):
		count_answer = num+1
	else:
		possible = [True]*10
		for i in exclude_nums:
			possible[i] = False
		max_num = find_max(num,possible)
		min_num = find_min(num,possible)
		if min_num is None:
			count_answer = len(str(max_num))+abs(num-max_num)
		else:
			count_answer = min(len(str(max_num))+abs(num-max_num),len(str(min_num))+abs(num-min_num))
print(min(count_answer,abs(100-num)))

yj10516 3년 전 0

444445

0 1 2 3 5 6 7 8 9

일때 느리긴 한데

무한루프가 있는지는 잘 모르겠습니다.

yj10516 3년 전 0

4*10^6번 find_max의 while문을 돌면 시간초과일까요?

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

문제

문제

출처

ICPC

11%에서 시간초과

alsrms27 3년 전 0

yj10516 3년 전 0

yj10516 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말