paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」の開発者が、プログラミングやITエンジニアの転職などについて書いています。

logo

ITエンジニア向け総合求人・学習サービス「paiza」の開発者が、プログラミングやITエンジニアの転職などについて書いています。

トップ > プログラミング-プログラミング初心者 > 初心者向け・難しそう？なプログラミング問題を簡単に解く方法【Python】

初心者向け・難しそう？なプログラミング問題を簡単に解く方法【Python】

プログラミング-プログラミング初心者 プログラミング-プログラミング学習 プログラミング

f:id:paiza:20190326193653j:plain
Photo by Phil Whitehouse
f:id:paiza:20180910132940p:plainこんにちは。倉内です。

paizaでは、プログラミング問題を解いてS・A・B・C・D・Eの6段階のランクでコーディングスキルを測るスキルチェックを提供しています。初めてプログラミングに触れた方には、まずDランクの問題から挑戦することをオススメしています。

恐らくpaizaラーニングなどで言語の入門レベルの知識を身につけた方は、Dランク問題はクリアできると思います。しかし、そのあとCランクを取得し、さらにBランク問題に挑戦！となると少しハードルが高いと感じるかもしれません。

そこで今回は先日こちらの記事で解答コードを公開した、ゲームイベントのBランク相当の問題を例に、解答にたどり着くためのプロセスを詳しく解説したいと思います。

はじめに

Bランク取得が難しいと感じている方の中にも「要求されていることは理解でき、プログラムも書けるがあと一歩ランクアップに及ばない（入力ケースなどの考慮漏れ）」と「問題文が何を言っているか理解するのが難しく、プログラムに落としこめない」に分かれると思います。今回は後者の方向けの解説となります。

これから解いていく問題はプログラミングゲーム『エンジニアが死滅シタ世界〜アンドロイドとふたりぼっちで生きろ〜』で出題している「高層タワー [MISSION LEVEL: B]」（スキルチェックのBランク相当）となります。

問題文：

単語を組み合わせて新単語を作ります。
新単語は N 個の文字列を、前から順に結合して作ります。
この時、冗長さをなくすため、 前から結合した単語の末尾 と 後ろの単語の先端 が一番長く一致するように結合します。
例えば、 入力例 1 の "paiza", "apple", "letter" の場合、先頭から "paiza", "apple" を条件どおり重ねると "paizapple" となります。
この単語を更に次の単語と重ねると "paizappletter" となります。
なお、必ず前から順番に重ねるため、 入力例 2 の "poh", "p", "oh" を結合する場合は、"poh" と "p" を重ねた後の単語 "pohp" と "oh" を重ね "pohpoh" となります。
N 個の単語が与えられるので、前から順番に単語を結合した場合の新単語を出力してください。

入力される値：
  • 1 行目に、結合する単語の数を表す整数 N が与えられます。
  • 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、 i 番目に結合する単語を表す文字列 w_i が与えられます。
  • 入力は合計 N + 1 行であり、最終行の末尾に改行が 1 つ入ります。
条件：
  • 2 ≦ N ≦ 100
  • 各 i (1 ≦ i ≦ N) に対して以下を満たす。

　・1 ≦ (w_i の長さ) ≦ 100
　・w_i は半角英小文字のみで構成されている。

解答コード（Python）：
n = int(input())
ans = ""

def check(S_1, S_2): #何文字目まで一致しているかを探す
    min_len = min(len(S_1), len(S_2))
    cnt = 0
    for i in range(min_len+1):
        if S_1[-1*i::] == S_2[:i:]:
            cnt = i

    return cnt

for i in range(n):
    tmp = input()
    check_count = check(ans, tmp)
    ans += tmp[check_count::]

print(ans)

上記の問題文と解答コードを見て「なるほどわからん」と思った方も、これからじっくり解説していきますので安心してください。

Bランク問題攻略のためには

問題にもよりますが、Bランクの問題はC・Dランクの問題と比べて問題文が長く複雑になっています。情報量が多いと言い換えてもいいでしょう。

なので、Bランク問題を解く場合は

問題文を理解する　→　情報を整理する　→　単純な処理に分解してコードを書いてみる　→　要求仕様に沿ってコードを書いてみる　→　テストしてみる　→　完成

というプロセスで考えていくことにします。

（補足）Aランク問題、Sランク問題になってくると処理を高速化するアルゴリズムを考える力が必要になります。Bランク問題でも大規模データの対処が必要になることはありますが今回は触れていません。

Bランク問題を解くプロセスを実践

1．問題文の理解と情報整理

まずは問題文を読み、必要な情報を整理します。

下図の書き方がベストというわけではないので、自分なりに整理して実装イメージがわけばよいです。私は紙に書き出すことが多いですね。疑問点などもメモしておきます。

単語を配列に入れて考えてみましたが、文字列の扱いはもっといい方法がありそうな気がしますね…。これはのちほど説明します。

さて、今回やらないといけないことは以下の3つと言えそうです。

①前の単語は末尾から、後の単語は先頭から何文字目まで一致しているかを探す。
②「前の単語と後の単語を比べる」と「単語の中の文字の一致を調べる」とでループを二重にしないといけない。
③文字の一致を探すためには比べている単語の文字数が少ない方を条件範囲にしないといけなそうだ。

Bランクの問題の多くはC・Dランク問題を解くためのループや条件分岐、配列などを組み合わせて解くことができます。そのためまずは「単純な処理に分解する」と考えるとよいでしょう。

2．どこが難しそうか見当をつける

これは1回コードを書いてみてからでもいいかもしれませんが、どこが難しそうかあたりをつけてみます。

私は「前の単語の末尾1文字」と「後の単語の先頭1文字」を見るだけなら簡単なのに、何文字目まで一致してるか探さないといけないのが面倒そうだなと思いました。

具体的に言うと…

paiza　と　apple　は
paizaの最後の「a」とappleの最初の「a」だけ一致している。

なんだ最後と最初が一致してるか見ればいいだけなら簡単…？

apple　と　letter　は
appleの後ろの2文字「le」とletterの最初の2文字「le」が一致している。

最後の文字「e」と最初の文字「l」を見るだけでは駄目そうです。

しかも、後の単語を"l"、"e"と2文字進めたとき、前の単語は末尾から"e"、"l"と2文字さかのぼって、そのあと"l"、"e"と見ないといけません。

ただ、何文字目まで一致しているかさえ分かれば、あとは単語をくっつけるだけです。

3．処理を段階的に考えてみる

ここからは実際にコードを書いていきますので、オンライン実行環境のpaiza.IOで実行しながら進みましょう。

とりあえず渡された単語N個をくっつけて1つの単語として出力するだけのコードを書いてみます。入力例1で実行してみると"paizaappleletter"と出力されます。

# 渡される単語の個数：N個
N = int(input())

# 答えとなる単語（くっつけたあとの単語）
ans = ""

# N個分の単語を受け取ってansに格納
# 問題の解答としては前後の単語の文字の一致を探す処理が必要
for i in range(N):
    ans += input()

print(ans)

次に取得した前の単語と後の単語を比べて、何文字目まで一致してるか探すコードを書きます……と言いたいところですが、

しかも、後の単語を"l"、"e"と2文字進めたとき、前の単語は末尾から"e"、"l"と2文字さかのぼって、そのあと"l"、"e"と見ないといけません。

これをうまく処理するために文字列のスライスを習得しておきましょう。

  • 通常のスライス

tmp = ["paiza", "apple", "letter"]

インデックスの考え方（正の値）
　文字と文字の間を示すため最初の文字の左端が0、最後の文字の右端が5

print(tmp[0][0:1])　←　paizaの0番目から1文字取り出すため"p"
print(tmp[0][:1])　←　始点・終点は省略可能なためこれも結果は"p"

インデックスの考え方（負の値）
　末尾の要素の左端を-1とする相対インデックスとなる

print(tmp[0][-1:])　←　paizaの末尾から1文字さかのぼった位置から取り出すため"a"
print(tmp[0][-3:])　←　paizaの末尾から3文字さかのぼった位置から取り出すため"iza"

  • 少し発展させたスライス

Pythonではi番目からj-1番目までの文字をk個ごとに取り出すという処理をシンプルに書くことができます。

word = "paizappletter" とします。

例えば文字列の0番目から6番目までの文字を2つおきに取り出す。

print(word[0:6:2])　←　出力結果は"pia"となる

ここでも負の値は使えます。

例えば文字列の末尾から-5番目までの文字を2つおきに取り出す。

print(word[-1:-5:-2])　←　出力結果は"rt"となる

[開始位置: 終了位置: 何個置きか]と覚えるとよいと思います。通常のスライスと同じく、[ : : 2]のように開始・終了の値を省略すると最初から最後までとなります。

スライスを使うと前の単語の末尾と後の単語の先頭の文字が一致してるか調べる処理が書けそうな気がしてきましたね！


上記を踏まえて、ここからは入力例1で正しい結果が出力されるコードを書いていきます。まず"paiza"と"apple"を比べます。

前の単語の"paiza"は末尾から、a, z, i, a, pと検索する必要があります。後の単語の"apple"は先頭から、a, p, p, l, eと検索する必要があります。

例えば、"apple"を先頭からa, pと2つ進めたときは、"paiza"はa, zと2つさかのぼった位置からz, aと見て、一致しているか確認する処理を書く必要があります。（ここでa, zとさかのぼったままの文字とa, pを比べるのではないことに注意です。）

先ほどのスライス「末尾からさかのぼった位置から○文字取り出す」が使えそうです。

何文字分さかのぼるかは前の単語と後の単語を1文字ずつ進めて見比べていけばよいでしょう。ただし、単語の文字数は有限なので何文字分見るかを指定する必要があります。ここで、以下の条件を思い出してください。

③文字の一致を探すためには比べている単語の文字数が少ない方を条件範囲にしないといけなそうだ。

これは例えば、"paizapple"と"letter"で処理をすることを考えれば分かるのですが、文字数が少ないほうの"letter"を末尾までチェックし終えたら"paizapple"のほうは"zapple"より前の"pai"をチェックしたところで一致するはずがないので少ない方を指定します。（単語が全部同じ長さなら関係ありませんが…）

そこでmin関数を使って比べる単語の少ないほうの文字数を取得します。

min_len = min(len(tmp[0]), len(tmp[1]))

さきほど見たとおり"paiza"の場合、スライスのインデックスは最初の文字"p"の左端を0、最後の文字"a"の右端を5と考えます。そのため単語内の最後の文字（末尾からたどるときは最初の文字）までチェックするにはfor文の範囲はmin_len+1となります。

for i in range(min_len+1):
    if tmp[0][-1*i::] == tmp[1][:i:]:

tmp[0]="paiza"に対しては、末尾（-1）からiの数だけさかのぼった位置からうしろまでの文字、tmp[1]="apple"に対しては、先頭からiの数だけ進めた文字が一致しているか確認する処理が書けました。

スライスが分かりづらい場合は、以下のように直感的に分かる名前をつけて変数に入れてみてもいいかもしれません。

for i in range(min_len+1):
    # 前の単語の末尾から検索する
    word_1_tail = tmp[0][-1*i::]
    
    # 後の単語の先頭から検索する
    word_2_head = tmp[1][:i:]

    if word_1_tail == word_2_head:


"paiza"と"apple"をくっつける処理も加えて以下のようになります。

# 渡される単語の個数：N個
N = int(input())

# 渡された単語を格納しておく配列
tmp = []

# 答えとなる単語（くっつけたあとの単語）
ans = ""

# N個分の単語を受け取ってtmpに格納
for i in range(N):
    tmp.append(input())

# paizaとappleの文字数のminを取る
min_len = min(len(tmp[0]), len(tmp[1]))

# 何文字目まで一致したか覚える
cnt = 0

for i in range(min_len+1):
    if tmp[0][-1*i::] == tmp[1][:i:]:
        print("何文字目まで一致したか？：" + str(i))
        # あとで使いたいのでcntに入れる
        cnt = i

# ansにpaizaを入れる
ans = tmp[0]

# ansに一致したところから後ろ、つまりppleを入れる
ans += tmp[1][cnt::]

# くっつけたあとの単語：paizapple
print(ans)


ゴールが見えてきました。上記にansとtmp[2]="letter"を同じように何文字目まで一致しているか見比べて、3つの単語をくっつけた単語を作る処理を足します。

# 渡される単語の個数：N個
N = int(input())

# 渡された単語を格納しておく配列
tmp = []

# 答えとなる単語（くっつけたあとの単語）
ans = ""

# N個分の単語を受け取ってtmpに格納
for i in range(N):
    tmp.append(input())

# paizaとappleの文字数のminを取る
min_len = min(len(tmp[0]), len(tmp[1]))

# 何文字目まで一致したか覚える
cnt = 0

for i in range(min_len+1):
    if tmp[0][-1*i::] == tmp[1][:i:]:
        print("paizaとappleは何文字目まで一致したか？：" + str(i))
        # あとで使いたいのでcntに入れる
        cnt = i

# ansにpaizaを入れる
ans = tmp[0]

# ansに一致したところから後ろ、つまりppleを入れる
ans += tmp[1][cnt::]

# ansとletterの文字数のminを取る
min_len = min(len(ans), len(tmp[2]))

# 何文字目まで一致したか覚える
cnt = 0

for i in range(min_len+1):
    if ans[-1*i::] == tmp[2][:i:]:
        print("paizappleとletterは何文字目まで一致したか？：" + str(i))
        # あとで使いたいのでcntに入れる
        cnt = i

# ansに一致したところから後ろ、つまりtterを入れる
ans += tmp[2][cnt::]

# くっつけたあとの単語：paizappletter
print(ans)

かなり冗長なコードではありますが、出力結果が想定通り"paizappletter"となりました。入力例1でなくとも3つの単語であれば出力結果は正しくなるはずなので、入力例2の単語でも正しい結果が得られます。

しかし、このまま提出してもCLEARはできないため、3つの単語固定ではなく渡される単語数に合わせて処理ができるように修正しましょう。

4．解答コードを書いてみる

先ほどのコードで修正しなければならないのは、単語数：Nで処理できるようにするところだけです。

# 渡される単語の個数：N個
N = int(input())

# 渡された単語を格納しておく配列
tmp = []

# 答えとなる単語
ans = ""

# N個分の単語を受け取ってtmpに格納
for i in range(N):
    tmp.append(input())

# 何文字目まで一致したか覚える
cnt = 0

# 単語数N分チェックする
for j in range(N):
    # 比較対象となっている単語の文字数のminを取る
    min_len = min(len(ans), len(tmp[j]))

    # 文字数分チェックする
    for i in range(min_len+1):
        if ans[-1*i::] == tmp[j][:i:]:
            cnt = i

    # ansにtmp配列のj番目の単語をcnt番目から入れていく
    ans += tmp[j][cnt::]

# くっつけたあとの単語
print(ans)

冒頭に載せた解答コードよりは冗長ですが、単語数：Nで処理できるようになりました。

5．提出前にテストをしてみる

先ほどのコードは入力例1、入力例2ともに正しい結果が得られ、単語数：Nでも処理できます。しかし、実はこのまま提出するとCLEARできません。誤った箇所を見つけるためには自分でテストケースを考えて試してみる必要があります。

ここでは以下の3ケース追加でテストすることにします。

（ⅰ）1つ目と2つ目が同じ単語、3つ目の単語に一致文字がある

3
paiza
paiza
apple

正しい結果が得られました。

paizapple


（ⅱ）1つ目と2つ目の単語は一致文字があるが、3つ目の単語は一致がない

3
apple
letter
abcd

おや……？誤りです。正しくは"appletterabcd"と出力される必要があります。

applettercd


（ⅲ）1つ目と2つ目の単語は一致がないが、3つ目の単語に一致文字がある

3
paiza
letter
terminal

これは正しいですね。どうやら前に一致があるときに、次の単語に進むとおかしな位置から判定しているようです。

paizaletterminal


よくよく見てみると、cntがループ文の中で初期化されないので2つ目の単語、3つ目の単語…と新しい単語を見ているにも関わらず、前に見た単語のcntを保持してしまっています。そこで以下のように修正しました。

# 渡される単語の個数：N個
N = int(input())

# 渡された単語を格納しておく配列
tmp = []

# 答えとなる単語
ans = ""

# N個分の単語を受け取ってtmpに格納
for i in range(N):
    tmp.append(input())

# 単語数N分チェックする
for j in range(N):
    # 何文字目まで一致したか覚える
    cnt = 0
    # 比較対象となっている単語の文字数のminを取る
    min_len = min(len(ans), len(tmp[j]))
    
    # 文字数分チェックする
    for i in range(min_len+1):
        if ans[-1*i::] == tmp[j][:i:]:
            cnt = i

    # ansにtmp配列のj番目の単語をcnt番目から入れていく
    ans += tmp[j][cnt::]

# くっつけたあとの単語
print(ans)

これで完成しました。入力例だけだと正しく思えたので、テストをしてみてよかった…という結果になりました。

ゲームイベントのほうでこのコードを提出するとCLEARになります！

ただし、もっとスマートな書き方もできるので、冒頭に載せた解答コードもぜひ参考にしてください。

まとめ

今回はBランク相当の文字列を扱う問題を取り上げて、少しずつ正解に近づいていくためのプロセスをご説明しました。

スキルチェックには文字列の問題だけでなく、計算やパズルを解くなどさまざまなタイプのプログラミング問題がありますが、考え方としては使える部分があると思います。

「初めてBランク問題を解く場合にどの問題を選べばいいか迷う…」という方は、平均スコアが高めで平均解答時間が短めの問題が挑戦しやすいので問題を選ぶ際に参考にしていただければと思います。

スキルチェックは時間制限があるため、もう少し練習してからチャレンジしたいという方は、もう1問ゲームイベントのBランク問題の解答コードを公開していますので先にそちらを解いてみてください。

paiza.hatenablog.com

過去のゲームイベントの問題と解答コードもいくつかブログで解説しています。（問題のランクはいろいろです。）

paiza.hatenablog.com

paiza.hatenablog.com





「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。

詳しくはこちら

paizaラーニング

そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。

スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。

詳しくはこちら

paizaのスキルチェック

paizaのおすすめコンテンツ

Webセキュリティ入門 ハッカー入門 Webセキュリティ講座がスタート！CVは内田真礼さん！ Python✕AI 機械学習入門講座 CVに上坂すみれさんを起用！人気の機械学習講座を公開中！ paiza転職 paiza新卒 EN:TRY paizaラーニング 記事内に記載している情報は、記事公開時点でのものとなります。 Copyright Paiza, Inc, All rights reserved.