글 읽기 - (파이썬) 두 가지 경우를 비교해주실 수 있나요???

osh1795 2년 전 0

제가 이 문제에 대해 2가지 풀이를 찾았습니다.

근데 #1의 경우 시간 초과가 떴고 #2는 맞았습니다.(둘 다 직접 숫자를 넣고 돌리면 답은 맞습니다.)

혹시 #1과 #2의 계산량 차이가 어디서 나는지 알 수 있을까요???

그리고 계산량을 확인하는 방법도 알 수 있을까요??

#0 공통부분 - 숫자 입력받기
a=int(input())
b=int(input())

#1 시간초과
#프로그래밍 생각: 구간내의 모든 숫자를 리스트에 넣고 
#for문을 이용하여 합성수를 찾아 다른 리스트에 넣고 최종적으로 전체에서 1과 합성수를 빼줌

case=[] #합성수를 넣을 리스트
al=[] #al 리스트에 구간 내 모든 숫자를 넣고 나중에 합성수를 제거해줄 예정
for i in range(a,b+1):
    al.append(i) #범위내의 모든 숫자를 리스트에 넣음
    for k in range(2,i): #소수 합성수 구분 과정
        if i in case: #만약 이미 합성수임이 판별됐는지 확인
            break #이미 있으면 다음 숫자로
        else: 
            if i%k==0: #만약 i가 1이 아닌 수를 소인수로 가짐 >> 합성수 리스트(case)에 넣음
                case.append(i)
for i in range(len(case)):
    al.remove(case[i]) #al리스트에서 모든 합성수를 제거함
if 1 in al:
    al.remove(1)
if len(al)==0: #만약 구간내에 합성수 없음 >> -1 출력
    print(-1)
else:
    print(sum(al))
    print(min(al))
    
#2 정답
#프로그래밍 생각: 소수는 약수로 1과 본인만을 갖음을 이용

s = [] #소수를 담을 리스트 생성

for i in range(a, b+1): # m~n
    cnt = 0 #약수의 걧수
    for j in range(1, i+1): 
        if i%j == 0: #i가 j로 나눠짐 >> cnt +1 (약수의 갯수 추가)
            cnt += 1
        else:
            continue
    if cnt == 2: #cnt=2의 의미: 1과 본인만 갖음
        s.append(i)
if len(s) == 0:
    print('-1')
else:
    print(sum(s))
    print(s[0])

kravi 2년 전 1

파이썬에서 특정 위치를 제거하는 연산은 제일 끝 원소(pop())가 아니라면 O(n)의 시간 복잡도를 가집니다.

(https://wiki.python.org/moin/T...)

이유를 대략적으로 설명하자면, 리스트는 선형적으로 이어져있는 구조인데 중간에 하나를 빼려면 나머지를 그 위치로 옮겨야 합니다.

가령 [1, 2, 3]이 저장되어있는 리스트에 첫 번째 원소인 1을 제거한다고 하면 (remove(1) 혹은 pop(0)) 우리가 보는 명령어는 한 줄이지만

내부적으로는 두 번째 원소인 2를 첫 번째 자리에, 세 번째 원소인 3을 두 번째 자리로 옮기는 과정을 거쳐야 합니다.

그래서 길이가 N인 리스트에서 원소를 제거하려고 들면 최악의 경우(첫 번째 원소를 제거하는 경우) N번의 옮기기 연산이 발생하고 시간 초과가 발생하게 됩니다.

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

문제

문제

출처

ICPC

(파이썬) 두 가지 경우를 비교해주실 수 있나요???

osh1795 2년 전 0

kravi 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말