[Python] 백준 2960번 - 에라토스테네스의 체

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

 

나의 답

import sys

N, K = list(map(int,input().split()))

cnt = 0
stack = []
P = 2

for i in range (2,N+1):
    stack.append(i)

while True:

    n = 1
    
    while (P*n <= stack[-1]):
        if P*n in stack:
            stack.remove(P*n)
            cnt+=1
        if cnt == K:
            print(P*n)
            sys.exit()
        n+=1
        
    P = stack[0]

 

제시 문제 그대로 풀었다.

2부터 N까지 스택에 담았다.

 

그리고 첫 소수 P는 2로 설정.

2의 배수를 순서대로 구해 지워나간다. stack의 마지막 값보다 작을 때까지만.

지울 때 카운트를 해준다.

카운트 값과 N번째 값이 같으면 지웠을 때의 값을 출력하면 된다.

 

2의 배수를 다 지웠다면, P는 3이 되고.. 3의 배수를 다 지웠다면, P는 5가 되고..

이런식으로 P의 값은 소수가 될 수 밖에 없다.

N번째 소수는 P의 값이 바뀔 때마다 카운트를 해줘서 구하면 될 듯 하다.

 

다른 사람 답
https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-2960-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4 참고

N, K = map(int, input().split())
tmp = 0
sieve = [True] * (N + 1)
for i in range(2, N + 1):
    for j in range(i, N + 1, i):
        if sieve[j] != False:
            sieve[j] = False
            tmp += 1
            if tmp == K:
                print(j)

 

아 굳이 값을 .. 스택에 다 넣어놓고 할 필요는 없었다....

True , False 값으로 구분해서 해도 충분하고 간결하다.

원리는 비슷한 것 같다.

근데 for문에서 모든 숫자를 두고 확인하다 보니 불필요하게 소수가 아님에도 불구하고 안쪽 for문이 돌아갈 것 같긴 하다.

 

Kotlin 버전 답

fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(' ').map { it.toInt() }

    var cnt = 0
    val stack = mutableListOf<Int>()
    var P = 2

    for (i in 2..N) {
        stack.add(i)
    }

    while (true) {
        var n = 1

        while (P * n <= stack.last()) {
            if (P * n in stack) {
                stack.remove(P * n)
                cnt++
            }
            if (cnt == K) {
                println(P * n)
                return
            }
            n++
        }

        P = stack[0]
    }
}

 

스택 만들 때

val stack = mutableListOf<Int>()

 

스택 추가할 때

stack.add(요소)

 

값 지울 때

stack.remove(요소)

 

마지막 값 확인할 때

stack.last()

 

인덱스로 접근할 때

stack[0] - 동일..