[백준 2960번] 문제풀이

문제

에라토스테네스의 체는 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 

7 3

예제 출력 1 

6

예제 입력 2 

15 12

예제 출력 2 

7

예제 입력 3 

10 7

예제 출력 3 

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

 

정답

 

문제를 풀고 다른 사람들의 풀이를 보았을때 deque를 사용해 문제를 풀이한 사람은 별로 없는것같다.

하지만 시간 복잡도는 O(n^2)으로 같으니 괜찮지 않으려나

 

"""
deque 짱
"""
import sys
# deque를 사용할거다
from collections import deque as de

input = sys.stdin.readline

# 배열의 범위를 정해주고 K값을 입력받는다.
n, k = map(int, input().split())
# 1부터 n의 값까지 정의된 deque를 만들어준다.
array = de(i for i in range(2, n+1))
# 결과값을 저장할 배열을 만들어준다.
result = []

# array에 값이 있다면
while array:
    # a는 배열의 첫번째 수이다
    # 배열의 첫번째 수는 소수 a의 배수를 모두 제거한 수 이므로 항상 소수일수밖에 없다.
    a = array[0]
    # array의 길이만큼 반복한다.
    for _ in range(len(array)):
        # 만약 array 가장 앞의 값이 a로 나머지 없이 나눠진다면.
        if array[0] % a == 0:
            # array의 첫번째 값을 추출해서 result에 넣어준다
            result.append(array.popleft())
        # 만약 소수 a의 배수가 아니라면
        else:
            # 배열을 한바퀴 회전시켜준다.
            array.rotate(-1)

print(result[k-1])