[Algorithm] 백준 - 27172번 수 나누기 게임 (Swift)

문제 소개

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

약수면 +1 나누어 떨어졌다면 -1 점을 갖게 되는 게임에서 결과를 출력하는 문제이다.

문제 풀이

이중 for 문으로 풀게 된다면 시간초과가 나게 된다. 따라서 다른 방법으로 풀어야 했다. 우선 길이가 1000001 인 nums 배열을 만들고, 어떠한 수가 등장했는지를 판별한다. 그리고 주어진 숫자의 배수를 판별하여 등장했다면 주어진 숫자에 +1 을 해주고 배수의 숫자에는 -1 을 해주면 된다.

import Foundation

let n = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { Int($0)! }
var nums = Array(repeating: false, count: 1_000_001)
var score = [Int: Int]()

for element in input {
    nums[element] = true
    score[element] = 0
}

for i in input.indices {
    let num = input[i]
    var j = 2
    
    while num * j <= 1000000 {
        if nums[num * j] {
            score[num, default: 0] += 1
            score[num * j, default: 0] -= 1
        }
        
        j += 1
    }
}

for element in input {
    print(score[element, default: 0], terminator: " ")
}