백준 9020번 Swift 알고리즘 연습

여전히 소수와 관련된 문제이다.

특정 짝수를 이루고 있는 두 개의 소수를 구하면 된다.

다만, 두 개의 소수가 각 값의 차를 계산했을 때 가장 작아야한다는 전제가 까다롭게 느껴졌다.

 

문제를 풀면서 시간 초과 오류가 가장 걱정이 됐기 때문에 이를 해결하기 위해서 최대한 고민을 해가면서 풀었다.

• 같은 값이 중복되어 더해졌을 경우 그 값의 차가 가장 적은 0이 나오기에... 중복값은 항상 그 값이 답이다..! 라는 사실도 나중에 풀면서 깨달았기 때문에 처음 제시했던 답안이 틀리곤 했다.
• count의 초기값을 1억으로 두었는데.. 알고리즘을 풀기 위함으로 셋팅해놓은 값이지만 내가 봐도 뭔가 깔끔하지가 않다... 더 좋은 방법으로 풀 수 있을 것 같다.

 

 

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

1. 특정 짝수 값을 입력했을 경우 그 짝수를 구성하는 두 개의 소수는 짝수보다 작을 것이다.
2. 때문에 입력받은 n보다 작은 값의 범위 내에서 소수를 전부 구해준다.
3. 그 후 범위 내의 소수 값을 위치를 번갈아가면서 한 번씩 더하여 입력받은 값 n을 만들 수 있는지 확인한다.
4. 만들어지는 수를 대상으로 차이를 구한뒤 가장 차이가 적은 값들을 value1, value2에 저장해둔다.
5. for 반복문이 끝나고 value1, 2를 출력한다.
6. 같은 소수 값이 중복되어 더해져도 되기 때문에 '3번' 과정을 진행할 때 범위 설정을 잘해준다.

 

 

* 9020번

let m = Int(readLine()!)!

for _ in 1...m {
    
    let n = Int(readLine()!)!
    var arr: [Int] = Array(repeating: 0, count: n + 1)
    var arr2: [Int] = []
    var count = 100000000
    var value1 = 0
    var value2 = 0
    
    for i in 2...n {
        arr[i] = i
    }
    
    for j in 2...n {
        for k in stride(from: j + j, through: n, by: j) {
            arr[k] = 0
        }
    }
    
    for k in 0...n {
        if arr[k] != 0 {
            arr2.append(k)
        }
    }
    
    for a in 0...arr2.count-1 {
        for b in a...arr2.count-1 {
            if arr2[a] + arr2[b] == n {
                if count > arr2[b] - arr2[a] {
                    count = arr2[b] - arr2[a]
                    value1 = arr2[a]
                    value2 = arr2[b]
                }
            }
        }
    }
  
    print("\(value1)" + " " + "\(value2)")
}

 

 

정리(Today I Learned)

1. 없음