백준 2581번 파이썬 - 소수

1. 문제 링크

https://www.acmicpc.net/problem/2581

2581번: 소수

---

2. 나는 어떻게 생각했는가? 

- 앞서 풀이를 올려놓은 1978번을 풀었다면, 무난하게 풀 수 있는 문제다.

- 약간의 생각만 더 하면 되는데, 그 부분이 시간초과에 관련된 부분이다. 

- 이중 FOR문을 사용하기 때문에 시간복잡도가 O(n제곱) 만큼 걸리기에, 

- 이를 최소화 해야 하는 방법을 생각해야 한다.

- 입력값 m과 n이 커질수록, 시간초과가 발생할 확률이 높아진다. 

- 그러므로 소수는 1과 자신, 총 2개의 약수만을 갖는다는 특성을 사용한다.   

m = int(input())
n = int(input())
case = []

for i in range(m, n + 1):
  yaksoo = 0
  for j in range(1, i + 1):
    if i % j == 0: 
      yaksoo += 1
      if yaksoo > 2: # 시간 초과를 막기위함.
        break
  if yaksoo == 2: 
    case.append(i)

if len(case) > 0:
  print(sum(case))
  print(min(case))
else:
  print(-1)

 

---

3. 코드 개선

- 내 제출을 확인해보면 시간이 1초 가까이 걸리는 것을 확인할 수 있다. 

- 제한시간이 1초이기 때문에 굉장히 아슬아슬한 것을 알 수 있다. 

- 코드 개선을 위해서 다른 분들의 풀이를 보고 새롭게 배운것이 있다. 

 

a) 메소드를 만들어라

- 메소드를 만들면 수행속도가 확연하게 차이가 나는 것을 확인할 수 있다. 

def YaksooList(start, end):
  case = []
  for i in range(start, end + 1):
    yaksoo = 0
    for j in range(1, i + 1):
      if i % j == 0: 
        yaksoo += 1
        if yaksoo > 2: # 시간 초과를 막기위함.
          break
    if yaksoo == 2: 
      case.append(i)
  return case


m = int(input())
n = int(input())
result = YaksooList(m, n)

if len(result) > 0:
  print(sum(result))
  print(min(result))
else:
  print(-1)

 

- 동일한 코드를 메소드로 정의해서 제출해보았다. 

 

- 1초대에서 0.6초대로 줄어든 것을 확인할 수 있다. 

- 왜 수행시간이 짧아지는지 아직은 잘 모르겠다. 

- 더불어, 어떻게 해야 더욱 메소드답게 코드를 짜는 건지도 모르겠다.

- 계속 연습해보면서 익혀나가야 할 것들이다.