ファイナル問題：商品の検索 (paizaランク C 相当)

このページについて

このページは、paiza ラーニング内に開設されているコンテンツ「レベルアップ問題集」で取り扱われているプログラミング課題について、独自の見解を述べたものです。

見解については、paizaラーニングの規約に基づき、許可されている範囲でのみ公開していますが、その内容については paiza とは一切関係なく、また paiza の立場を反映したものではありませんのでご注意ください。

挑戦する課題

レベルアップ問題集のデータセット選択メニューから「ファイナル問題：商品の検索 (paizaランク C 相当) 」を取り上げます。

以下は、問題公開 Web ページからの引用です。

問題

N 個の文字列が入った、配列 S が与えられます。各 1 ≦ i ≦ Q に対して、以下の質問に答えてください。

文字列 T_i が与えられます。 S_j == T_i となる最も小さな j を出力してください。ただし、 S の中に T_i がない場合は -1 を出力してください。

入力される値

N Q
S1
S2
...
S_N
T1
T2
...
T_Q

N Q

...

S_N

...

T_Q

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。

期待する出力

S_j == T_i となる最も小さな j を出力してください。ただし、 S の中に T_i がない場合は -1 を出力してください。

j1
j2
...
j_Q

...

j_Q

入力例1

3 2
a
b
c
b
d

3 2

出力例1

2
-1

-1

考え方

この問題も辞書を使うと割合簡単に解ける問題です。
キー（ key）に対応づける値（ value）が存在するような問題の場合、辞書（言語によっては連想配列）を使うのが分かりやすく解く方法となります。

まず、先頭行から N と Q に相当する値を取り出しますが、 Q 行分のデータは AnyIterator を使って自動的に取り出しますので必要ありません。
したがって、先頭行からは N に相当する値だけを取り出します。

準備する辞書ですが、単語名を key とし、出現順位を value とするので、 [String: Int] 型の辞書を作ります。 [:] を代入することで初期化しますが、この状態では key も value もない辞書となりますので、それに注意するようにしてください。

まず最初に、 N 行分商品データを読み込みます。
読込んだ商品名に相当する単語を key として辞書を検索しますが、辞書に該当する key が存在しない場合には nil が戻りますので、その状態を guard 文で判断します。
通常、 guard 文はエラー発生時の早期リターンの目的で使うことが多いと思いますが、このような使い方も可能です。
ただし、 guard 文の中には return ではなく、 for-in 文をつづきから再開させるため continue を置くことに注意してください。

もう一点注意しなければならないのは、 key と関連づける番号、つまり value は出現順ではなく、「通し番号」である点です。
たとえば、

a
a
b

という入力があった場合、対応づける番号は

a -> 1
b -> 2

1 2	a -> 1 b -> 2

ではなく、

a -> 1
b -> 3

1 2	a -> 1 b -> 3

だという点です。

商品名を取り込んだら、マッチングさせるデータを AnyIterator を使って全て取り込みます。

取り込んだ全ての要素それぞれに対し、取り込んだ単語が辞書に登録されているか否かを判断します。
登録されていれば、その単語に対応した value を表示しますし、登録されていなければ -1 を出力します。

解答例

// 商品の数 N
// Q は必要ないので使わない
var n = readLine()!
        .split(separator: " ")
        .map { Int($0)! }
        .first!

// 初出の商品番号を入れる辞書        
var items:[String: Int] = [:]

// N 行目まで読み込む
for i in 0..<n {
    let s = readLine()!
    
    // 辞書に未登録の商品だった場合
    guard let _ = items[s] else {
        // 先頭からの通し番号を入れる
        items[s] = i + 1
        continue
    }
}

// 1. 残りの行を全て読み込む
// 2. Stringに変換する
// 3. 各行ごとに処理を行う
// 3-1. 辞書に登録されていれば、関連づけられた通し番号を表示
// 3-2. 登録されていなければ、-1 を表示
Array(AnyIterator { readLine() })
    .forEach { s in 
        if let i = items[s] {
            print(i)
        } else {
            print(-1)
        }
    }

// 商品の数 N

// Q は必要ないので使わない

var n = readLine()!

.split(separator: " ")

.map { Int($0)! }

.first!

// 初出の商品番号を入れる辞書

var items:[String: Int] = [:]

// N 行目まで読み込む

for i in 0..<n {

let s = readLine()!

// 辞書に未登録の商品だった場合

guard let _ = items[s] else {

// 先頭からの通し番号を入れる

items[s] = i + 1

continue

}

// 1. 残りの行を全て読み込む

// 2. Stringに変換する

// 3. 各行ごとに処理を行う

// 3-1. 辞書に登録されていれば、関連づけられた通し番号を表示

// 3-2. 登録されていなければ、-1 を表示

Array(AnyIterator { readLine() })

.forEach { s in

if let i = items[s] {

print(i)

} else {

print(-1)

}