자료구조 및 알고리즘/백준

[python] 2960. 에라토스테네스의 체

viamemine 2024. 5. 28. 23:25
728x90
반응형

 

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

 

풀이

 

 

이번 문제는 어렵지 않았지만 코드가 조금 지저분하게 작성됐습니다.

 

시간 제한은 1초로, 이중 for문으로 충분한 시간이라 이중 for문으로 구현했습니다.

 

그러나, cnt를 셀 때마다 k랑 맞는지 확인하고 

break를 걸어주어야 하는 부분 때문에 코드가 지저분해졌고 'if ~' 부분을 반복해서 작성했습니다. 

 

따라서 방향성을 바꿔서 깔끔한 코드로 수정했습니다.

 

또한 이중for문을 완전히 탈출할 때 if문을 두 번 쓰지 않고, 

하단의 코드처럼 else: continue break로 작성해도 됨을 배웠습니다.

 


 

- 지저분한 코드

n, k = map(int, input().split())

num_list = [i for i in range(2, n+1)]

cnt = 0
for j in range(len(num_list)):
    p = min(num_list)
    num_list.remove(p)
    cnt += 1
    if cnt == k:
        print(p)
        break

    for i in num_list:
        if i % p == 0: # i가 p의 배수일 때
            num_list.remove(i)
            cnt += 1
            if cnt == k:
                print(i)
                break

    else: # if cnt == k: 대신 사용 (이중포문 완전히 탈출할 때)
        continue
    break

 


 

- 깔끔한 코드 (i의 배수를 이렇게 쓰는거다 - !)

n, k = map(int, input().split())
num_list = [True] * (n+1)

cnt = 0
for i in range(2, n+1):
    for j in range(i, n+1, i): # i의 배수
        if num_list[j] != False:
            num_list[j] = False # False로 삭제를 표현
            cnt += 1
            if cnt == k:
                print(j)

 

 

 

728x90