Solved.ac 클래스 2 마무리

Today 1/14

이항 계수 1 (My Code)

let NK = readLine()!.split(separator: " ").map{Int(String($0))!}

func factorial(_ n: Int) -> Int {
    if n == 0 { return 1 }
    return n * factorial(n-1)
}
print(factorial(NK[0])/(factorial(NK[1]) * factorial(NK[0]-NK[1])))

이를 만족시키는 이항 계수를 구하는 문제이다. 0이 될 경우는 문제에서 이미 범위를 두어 생각할 필요가 없으므로, 팩토리얼 부분만 구현하면 된다.

재귀함수로 구하니 간단한데도 시간이 많이 걸려서 수정해봤다.

let NK = readLine()!.split(separator: " ").map{Int(String($0))!}

func factorial(_ n: Int) -> Int {
    return n == 0 ? 1 : Array(1...n).reduce(1,*)
}
print(factorial(NK[0])/(factorial(NK[1]) * factorial(NK[0]-NK[1])))

배열 자체를 Array(1...n) 식으로 정의해주어도 된다는 것을 처음 알았다.

요세푸스 문제 0 (My Code)

let NK = readLine()!.split(separator: " ").map{Int(String($0))!}
var circle = Array(1...NK[0])
var count = 1
var index = 0
var output = [Int]()

while output.count != NK[0] {
    if circle[index] != 0 {
        if count == NK[1] {
            output.append(circle[index])
            circle[index] = 0
            count = 1
        } else {
            count += 1
        }
    }
    index += 1
    if index == NK[0] {
        index = 0
    }
}
print("<\(output.map{String($0)}.joined(separator: ", "))>")

배열을 하나씩 돌아가면서 뽑힌 수들은 0으로 만들어 돌렸는데, 나머지를 이용한 방법이 더 빨라서 더 공부했다.

요세푸스 문제 0 (Ohters Code)

let NK = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N,K) = (NK[0], NK[1])
var circle = Array(1...N)
var answer = [Int]()
var index = -1

while true {
    index = (index + K) % circle.count
    answer.append(circle[index])
    circle.remove(at: index)
    if circle.count == 0 {
        break
    }
    index = (index - 1 + circle.count) % circle.count
}

print("<\(answer.map{String($0)}.joined(separator: ", "))>")

Hashing (My Code)

let _ = Int(readLine()!)!
var inputArr = readLine()!.map{Int(Character(String($0)).asciiValue!)-96}
var result = inputArr.enumerated().map{$0.1 * Int(pow(31.0, Double($0.0)))}.reduce(0, +) % 1234567891
print(result)

자꾸 50점이 떠서 왜 그런지 살펴봤더니 두 가지 이유가 있었다.

1. pow() 함수를 사용해서 괜히 불러오는데에 시간이 많이 걸렸다.
2. r이 M(1234567891)보다 클 때, 그 나머지로 계산해야 엄청나게 큰 수의 계산을 피할 수 있는데 아래를 참고했다.

boj 15829 Hashing c++

let _ = Int(readLine()!)!
var inputArr = readLine()!.map{Int(Character(String($0)).asciiValue!)-96}
let M = 1234567891
var r = 1
var result = 0
inputArr.enumerated().forEach { index, num in
    if r > M {
        r %= M
    }
    result += num * r
    r *= 31
}
print(result < 1234567891 ? result : result % 1234567891)

그것들을 기반으로 다시 작성한 코드

마인크래프트 (My Code)

let NMB = readLine()!.split(separator: " ").map{Int(String($0))!}
var groundArr = [Int]()
for _ in 0..<NMB[0] {
    let ground = readLine()!.split(separator: " ").map{Int(String($0))!}
    groundArr += ground
}

let min = groundArr.min()!
let max = groundArr.max()!
var bestTime = Int.max
var bestHeight = Int.max

for height in min...max {
    var time = 0
    var B = NMB[2]
    for index in groundArr {
        if index < height {
            let gap = height - index
            time += gap
            B -= gap
        } else {
            let gap = index - height
            time += (gap * 2)
            B += gap
        }
    }
    if B < 0 {
        break
    } else {
        if time < bestTime {
            bestTime = time
            bestHeight = height
        } else if time == bestTime {
            if height > bestHeight {
                bestTime = time
                bestHeight = height
            }
        }
    }
}
print("\(bestTime) \(bestHeight)")

브루트 포스로 푸는거라는 힌트를 얻고, 가장 높이가 낮은 것과 높은 것 사이에서 조건문을 돌리면 되겠다고 생각했다. 또, 배열과 배열을 합칠 때에는 append 대신 += 를 써서 간단하게 합칠 수 있다는 것도 알았다.

예외처리는 귀찮긴 했지만 그렇게 어렵진 않았다.