백준 4948번 Swift 알고리즘 연습

베르트랑 공준이라는 개념이 나오는 문제이다.

결국 입력받는 값 ~ 입력받는 값 * 2 의 범위 내에서 소수를 찾아 카운팅하면 된다.

문제의 난이도는 에라토스테네스의 채만 이해하고 있으면 금방 풀만한 난이도였던 것 같다.

하지만 이번에도 시간 초과 오류가 발생하여 꽤나 여러번 삽질을 했다...

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 에라토스테네스의 채 개념을 적용하기 위해서는 2이상의 수부터 시작하는 것이 좋겠다는 생각이 들었다.
2. 그래서 입력받는 값을 최대 값으로 설정하고 (2*n) 0 ~ 2*n의 범위 내에 모든 소수를 도출했다.
3. 그 후 입력받은 n부터 2*n의 범위 내에 있는 소수 값들만 counting 해주면 끝.

 

위와 같은 방식으로 진행했지만 처음에 시간 오류가 났다.

n이 0일 경우 break 해주는 if 문에 print(count)까지 입력을 해준 것이 문제였던 것 같다.

심지어 처음엔 if 문이 맨 마지막에 있었기 때문에 0을 입력 받았을 경우 바로 break 되지 않고 한 번 더 사이클을 도는 것이 미세하지만 차이를 만들었을지도..!

 

 

* 4948번

for _ in 1... {

let n = Int(readLine()!)!
var arr: [Int] = Array(repeating: 0, count: 2 * n + 1)
var count = 0

    if n == 0 {
        break
    }

for i in 2...2 * n {
    arr[i] = i
}

for j in 2...2 * n {
    for k in stride(from: j + j, through: 2 * n, by: j) {
        arr[k] = 0
    }
}

for k in n+1...2*n {
    if arr[k] != 0 {
        count += 1
    }
}
        print(count)
}

 

정리(Today I Learned)

1. 알고리즘을 풀다보니 내가 보기 쉽게 그냥 단순 변수명으로 정해놓고 푸는 경우가 있는데... 앞으로는 좀 더 변수명에 신경써서 다시 알고리즘을 봤을 때 헷갈릴 수 있는 부분을 최소화 해야겠다는 생각이 든다.