はじめに

初めまして、26卒の就活生です。
私は普段SwiftUIを使ったiOSアプリ開発を行っていますが、コーディングテストというものに対する対策を全くしていなかったので、記事にして復習する機会とします。
なお、今回は予約サービスや料金計算などの実装問題ではなく、基本的な入力の受け取り方と、アルゴリズム問題に出そうな問題の基礎について書き残します。

標準入力からの受け取り

まずは、必ずコーディングテストで必要となる標準入力の受け取り方についてです。

文字列の受け取り

例えば、文字列を受け取りたい場合です。

input.txt

こんにちは

という入力を受け取っていましょう。

main.swift

let hello = readLine()!
print(hello)

上記を実行すると、「こんにちは」が出力されます。
「!」をつけなければいけないのは、標準入力はoptionalとなるからです。
~~nilを許容する状態なので、実際の開発ではやらないほうがいいですが、コーディングテストだからまぁ？~~

数値の受け取り

実際のコーディングテストの大半はこちらを使うでしょう。

input.txt

main.swift

let num = Int(readLine()!)!
print(num)

出力結果は100となります。1行に「 ! 」マークが二つ出てくるなんて、、

入力が1行、空白区切りで渡された場合は、split(separator: " ")を使いながら、丁寧に受け取ります。

input.txt

3 5

main.swift

let line = readLine()!.split(separator: " ").map { Int($0)! }
let h = line[0]
let w = line[1]

print("行数: \(h), 列数: \(w)")

なんでもいいですが、コーディングテストで行数が最初、次に列数が与えられることが多いので、こういう例にしてみました。

二次元配列の宣言

二次元配列を宣言してみましょう。

行数 h = 3
列数 w = 5
として書いてみます。

main.swift

let h = 3
let w = 5

var matrix = Array(repeating: Array(repeating: 0, count: w), count: h)
for items in matrix {
    let item = items.map { String($0) }.joined(separator: " ")
    print(item)
}

出力.

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

動的計画法

アルゴリズム問題で動的計画法がよく出てきます。
個人的にとても難しいと思っています。
例題を2問見ていきます。

階段を登る問題

階段の総数 n が与えられます。
一度に一段または二段登れる時、何通りありますか？

climbStairs.swift

func climbStairs(_ n: Int) -> Int {
    //基底条件
    if n <= 2 { return n }

    var dp = [Int](repeating: 0, count: n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in 3...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    print(dp)   //デバック用
    return dp[n]
}

print("階段の総数を教えてください。")
let n = Int(readLine()!)!
print(climbStairs(n))

例として、最大段数として5を与えます。

出力. (n = 5)

階段の総数を教えてください。
5
[0, 1, 2, 3, 5, 8]
8

階段の段数が5の場合、登り方の組み合わせは8通りあることがわかります。

ナップサック問題

与えられた4つの（重量,価値）において、最大重量7を超えない最大の価値を求めます。
入力の1行目の左側はアイテム数、右側はナップサックがもてる最大重量です。
2行目からは各アイテムの情報が与えられ、（重量, 価値）という形で渡されます。

input.txt

この入力例の場合は、

アイテム数 n = 4
最大重量 maxWeight = 7
となりますね。

maxKnapsackValue.swift

unc maxKnapsackValue() -> Int {
    var dp = Array(repeating: Array(repeating: 0, count: maxWeight + 1), count: n + 1)
    print("--- 初期状態 ---")
    for item in dp {
        print(item)
    }
    //アイテム数で繰り返し
    for i in 1...n {
        let weight = items[i - 1].weight
        let value = items[i - 1].value
        for w in 0...maxWeight {
            if w >= weight {
                //アイテムを選ぶ場合と選ばない場合の最大値を取る
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }
    print("--- デバック ---")
    for item in dp {
        print(item)
    }
    print("------")
    return dp[n][maxWeight]
}

// 標準入力からデータを取得
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let maxWeight = firstLine[1]

//各アイテムの読み込み
var items = [(weight: Int, value: Int)]()
for _ in 0..<n {
    let item = readLine()!.split(separator: " ").map { Int($0)! }
    items.append((weight: item[0], value: item[1]))
}

print(maxKnapsackValue())

出力.

--- デバック ---
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 13, 13, 13, 13, 13]
[0, 0, 0, 13, 13, 13, 13, 21]
[0, 0, 6, 13, 13, 19, 19, 21]
[0, 0, 6, 13, 13, 19, 25, 25]
25

したがって、今回の例ですと、25がナップサックが抱えられる最大の価値になりました。

さいごに

難しいです...