BOJ 2960 에라토스테네스의 체 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

에라토스테네스의 체: n보다 작거나 같은 모든 소수를 찾는 알고리즘.

1. 2부터 n까지 모든 정수를 적는다
2. 아직 지우지 않은 수 중 가장 작은 수 찾기. 이걸 p라고 하고, 이 수는 소수임.
3. p를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지운다
4. 아직 모든 수를 지우지 않았다면 다시 2번 단계로 간다.

n, k가 주어졌을 때 k번째 지우는 수를 구하는 프로그램 작성.

입력

• n, k가 주어짐(1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

• k번째 지워진 수를 출력.

두 번째 단계 (문제 핵심 파악)

1. 2~n까지 정수가 담긴 리스트를 만든다.
2. 가장 작은 수를 p라고 할때, p는 소수임.
3. p를 리스트에서 삭제하고, 리스트에 남아있는 p의 배수를 크기순으로 지운다.
4. 이때, p가 1st, p의 배수 중 첫번째 요소가 2nd, p의 배수 중 2번째 요소가 3rd 순이다.
5. 이때 리스트가 비어있지 않다면(while 리스트) 다시 2번으로 가서 단계를 지속한다.

코드 작성

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
cnt = 0 # 순서 카운트

# 2부터 n 까지
lst = [i for i in range(2, n + 1)]

while len(lst) != 0:
 # 가장 작은 수 : p
 min_num = lst[0]
 baesu_lst = []

 for j in range(len(lst)): # 2~7
 if lst[j] % lst[0] == 0:
 # lst.remove(lst[j])
 baesu_lst.append(lst[j])
 cnt += 1
 if cnt == k:
 print(baesu_lst[-1])
 break
 if cnt == k:
 break
 lst = [x for x in lst if x not in baesu_lst]

느낀점

첫번째 시도에서,

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
cnt = 0 # 순서 카운트

# 2부터 n 까지
lst = [i for i in range(2, n + 1)]

while len(lst) != 0:
 # 가장 작은 수 : p
 min_num = lst[0]
 baesu_lst = []

 for j in range(len(lst)): # 2~7
 if lst[j] % lst[0] == 0:
 # lst.remove(lst[j])
 baesu_lst.append(lst[j])
 cnt += 1
 if cnt == k:
 print(baesu_lst[-1])
 break
 lst = [x for x in lst if x not in baesu_lst]

if문을 for문 밖으로 빼서, cnt가 k와 같을때 멈춰야 하는데 그러지 못하고 계속 반복문을 돌았다.

따라서 if문을 for문 안으로 넣어서 for문의 종료조건을 만족시켰으며 if문을 밖으로 빼서 while 문의 종료조건을 만족시켰다.

리스트를 구할 때 위처럼 리스트 컴프리헨션을 이용하니 코드가 짧아진 데서 오는 안정감과 가독성이 있는거 같다.(유용하게 쓰자)

사실 첫번째 코드는 test case는 모두 통과해서 정답인줄 알았지만, 제출 시 17%에서 오답이었고, 반례를 찾는 실력까지는 도달을 못해서 chatGPT가 10 3 가 반례임을 제시해서 이를 이용해서 완전한 코드가 되었다.

반례 찾는 연습 해봐야지(어떻게?)

반례 찾기

(https://velog.io/@juyeonma9/%EB%B0%B1%EC%A4%80-%EC%9E%90%EC%A3%BC%ED%8B%80%EB%A6%AC%EB%8A%94%EC%9A%94%EC%9D%B8)

• 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. https://www.acmicpc.net/problem/14405 를 예로 들어 봅시다. 그러면 이런 입력들을 넣어 볼 수 있습니다.
  • pi 하나만 넣으면? ka? chu? 한 글자만 넣으면? p? k? c? i? a? r?
  • pika는 YES가 나와야 합니다. 이걸 조금 변형하면? pik? pia? pka? piak? pkia? ipka? kipa? pikaa? pikka? piika? ppika?
  • kapi도 YES가 나와야 합니다. 이걸 조금 변형하면? kap? kai? api? kaip? kpai? kapii? kaapi?
  • 주어진 예제를 조금 변형하면? pikap? pikpi? pipikach? pipikaphu?
  • 그냥 정말로 아무거나 넣으면? abcd? pipichukachuka? pichaku? ppap? pikach?
• 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등의 최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. 위에서 언급한 "피카츄" 문제의 경우 p, k 등의 한 글자짜리 입력이 여기에 해당되겠죠.
• N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.