백준 4948번 python 풀이 (with for-else)

 

단계별로 풀어보기를 하기 때문에 비슷한 문제들이 묶여있기에

이전 문제들을 풀고나서 해당 문제도 쉽게 풀 수 있을줄 알았다

 

하지만 시간초과가 자꾸 나서 질문게시판을 뒤져봤다

 

<초기코드>

import math

def find_prime(m):
  if m == 0 or m == 1:
    return False
  for i in range(2, int(math.sqrt(m)) + 1):
    if m % i == 0:
      return False
  return True

while True:
  l = []
  n = int(input())
  if n == 0:
    break
  else:
    for i in range(n+1, 2*n+1):
      if find_prime(i):
        l.append(i)
    print(len(l))

 

반복문이 계속되면 매번 소수를 새로 찾아야하기에 그 부분에서 시간이 초과된 것

=> 이미 특정범위에서 소수를 찾았다면 또 다시 함수를 통해 소수를 찾지않고

      미리 발견된 소수를 발견시에 딕셔너리에 저장하여 딕셔너리에서 찾아서 카운트함

 

전에 알고리즘 문제 풀다가 리스트에서 찾는 것보다 파이썬에선 딕셔너리가 훨씬 빠르다는 것을 본 적이 있음

=> 인덱스를 설정하는게 어렵지 않으면 이왕이면 딕셔너리를 사용

(특정한 키값을 지정하지 못하고 인덱스 호출이 필요할 경우 리스트 사용)

 

<중간코드1>

import sys, math

def find_prime(m):
  if m == 0 or m == 1:
    return False
  for i in range(2, int(math.sqrt(m)) + 1):
    if m % i == 0:
      return False
  return True

while True:
  d = {}
  n = int(sys.stdin.readline())
  c = 0
  if n == 0:
    break
  else:
    for i in range(n+1, 2*n+1):
      if i in d:
        if d[i] == True:
          c += 1
      else:
        if find_prime(i):
          d[i] = True
          c += 1
    print(c)

 

딕셔너리를 이용해서 코드를 짰는데 아직도 시간초과가 떴기에...

다른분의 코드를 참고해서 다시 코드를 짜봤는데...

 

<중간코드2>

import sys

d = {}

while True:
  c = 0
  n = int(sys.stdin.readline())
  if n == 0:
    break
  else:
    for i in range(n+1, 2*n+1):
      if i in d:
        if d[i] == True:
          c += 1
      else:
        for j in range(2, int(i**0.5)+1):
          if i % j == 0:
            d[i] = False
            break
        else: #이 부분이 이해가 안됐던 부분
          c+= 1
          d[i] = True
    print(c)

참고한 코드 출처 url: https://www.acmicpc.net/board/view/109405

 

물론 해결은 됐다

이 과정중에 for문과 같은 반복문과 else를 사용할 수 있다는 점도 알게 되었다

(관련 참고 글: https://wikidocs.net/190098#google_vignette)

 

하지만 내가 짠 코드를 이용해서 정답을 제출하고 싶어서 미련이 남았고...

다시 본순간 어떻게 짜면 될지 깨달아버렸다...!!

 

문제점은

1. 딕셔너리를 while문 안에 넣어버려서 딕셔너리가 반복할때마다 초기화 됨

2. 소수가 아닌 수를 판별했을때 딕셔너리에 넣지않아 다수를 딕셔너리에서 제외하여 반복시 계산하는 수가 많아짐

이라고 생각했다

 

글을 쓰면서 다시 깨달은 점은

어차피 딕셔너리에서는 True인 수만 찾기 때문에

소수가 아닌 수는 딕셔너리에 넣어주지 않는 것이 더 빠를것이라 생각이 들었다

(딕셔너리에서 소수를 찾는 부분에서 if i in d 이부분말이다)

 

최종결과를 제출하고 False부분도 빼고 제출해봤는데 둘다 정답이었고

False를 딕셔너리에 넣지않으면 메모리는 덜 찍혔지만, 시간은 더 찍혔다

 

둘의 차이는 딕셔너리의 크기 차이

1) 만약 False값도 딕셔너리에 넣는다면

=> True False 판별하는 부분에서 이미 있는 값은 False일지라도 함수를 덜 호출하기 때문에 시간이 덜걸리지만

     딕셔너리의 값이 범위별로 계속 커지기 때문에 메모리를 많이 먹음...

2) False값을 딕셔너리에 넣지 않는다면

=> 딕셔너리 크기가 작아지기에 먹는 메모리도 적은 것 같다... 대신 소수 이외의 값은 무조건 함수를 거치기 때문에

      시간은 더 드는 것...

 

결론은

메모리나 시간에 따라 적절히 제외/첨가 하여 사용하면 될것 같다

 

<최종코드>

import sys, math

def find_prime(m):
  if m == 0 or m == 1:
    return False
  for i in range(2, int(math.sqrt(m)) + 1):
    if m % i == 0:
      return False
  return True

d = {}
while True:
  n = int(sys.stdin.readline())
  c = 0
  if n == 0:
    break
  else:
    for i in range(n+1, 2*n+1):
      if i in d:
        if d[i] == True:
          c += 1
      else:
        if find_prime(i):
          d[i] = True
          c += 1
        else:
          d[i] = False #이부분이 메모리 or 시간을 결정하는 부분
    print(c)