実行速度を考える

スキルチェックができるということでpaizaというサイトで勉強をしているのですが、こんな問題があった。

銀行 | レベルアップ問題集

paizaにはプログラミングスキルチェックの問題があり、正解するとランクがアップするのですが、

問題及び提出コード、ヒントをブログやSNS等に掲載しない
解答やヒントを教えてもらったり他人のコードを利用しない
複数アカウントで事前に問題を見るなどの不正行為をしない

という条件があるのでここには書けません。

しかしレベルアップ問題集は

このコーナー内の問題については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
授業や研修にもご利用いただけますので、ぜひ教材などにもお使いください。

ということなので、ネタに使わせていただきます。

Contents

1 問題の趣旨
2 ダメな方法
3 Dictionaryで時間短縮

問題の趣旨

銀行 | レベルアップ問題集

問題の内容は

取引先の会社が暗証番号を引き出す金額を伝えてくるので、会社名が銀行の名簿に登録されており、かつ会社側が会社の口座の暗証番号を正しく伝えてきた場合にのみ現金を支払う。全ての取引が終了した後の全ての会社の残高を出力せよという内容です。

最初に入力されるのは半角スペースで区切られた2つの数、NとK。Nは銀行に登録されている会社の数でKは取引の数です。
つぎのN行で銀行に登録されている会社名とその口座の暗証番号と残高についての情報が半角スペース区切りで入力され、そのあとのK行で取引を行おうとした会社の名前、伝えられた暗証番号、引出そうとした金額が半角スペース区切りで入力されます。

もし入力が以下のようになっていれば

3 5
A 0000 10000
B 1234 23456
C 5678 98765
A 0101 1000
B 1234 1000
C 5678 90000
A 0000 200
B 1233 10000

A社の暗証番号は0000、口座の残高は10000円、
B社の暗証番号は1234、口座の残高は23456円、
C社の暗証番号は5678、口座の残高は98765円、

そのあと

A社は暗証番号は0101で1000円ひきだそうとしたが、暗証番号が正しくない。
B社は暗証番号は1234で1000円ひきだそうとしたが、暗証番号は正しいので残高を1000円減らす。
C社も正しい暗証番号で90000円ひきだそうとしているので、残高を90000円減らす。
A社は正しい暗証番号で200円ひきだそうとしているので、残高を200円減らす。
B社は不正な暗証番号で10000円ひきだそうとしたのでなにもしない。

最後に残高を表示するのですが、結果を登録した順（この場合はA、B、C）で表示せよという条件がつけられています。

最初にNとKが入力されるので取得します。このときの前提として「半角スペースで区切られた2つの数字以外が入力されることはない」ことが保証されているので以下でNとKが取得できます。

class Program
{
    static void Main()
    {
        string[] nk = Console.ReadLine().Split();
        int N = int.Parse(nk[0]);
        int K = int.Parse(nk[1]);
        // これでNとKが取得できる
    }
}

class Program

{

static void Main()

{

string[] nk = Console.ReadLine().Split();

int N = int.Parse(nk[0]);

int K = int.Parse(nk[1]);

// これでNとKが取得できる

}

そのあとN回、標準入力で銀行に登録されている会社名とその口座の暗証番号と残高が入力されます。ループ文をつかって会社名、パスワード、残高を取得します。問題は取得したらどうするかです。

for(int i=0; i< N; i++)
{
    string[] vs = Console.ReadLine().Split();
    string name = vs[0];
    string password = vs[1];
    int money = int.Parse(vs[2]);

    // さあ、どうする？
}

for(int i=0; i< N; i++)

{

string[] vs = Console.ReadLine().Split();

string name = vs[0];

string password = vs[1];

int money = int.Parse(vs[2]);

// さあ、どうする？

}

ダメな方法

これまでの私ならクラスをつかって情報を保存することになります。

public class Company
{
    public Company(string name, string password, int money)
    {
        Name = name;
        Password = password;
        Money = money;
    }

    public string Name = "";
    public string Password = "";
    public int Money = 0;
}

public class Company

{

public Company(string name, string password, int money)

{

Name = name;

Password = password;

Money = money;

}

public string Name = "";

public string Password = "";

public int Money = 0;

}

上記のクラスをつくってから・・・

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        string[] nk = Console.ReadLine().Split();
        int N = int.Parse(nk[0]);
        int K = int.Parse(nk[1]);

        List<Company> companys = new List<Company>();
        for (int i=0; i< N; i++)
        {
            string[] vs = Console.ReadLine().Split();
            string name = vs[0];
            string password = vs[1];
            int money = int.Parse(vs[2]);

            companys.Add(new Company(name, password, money));
        }

        for (int i = 0; i < K; i++)
        {
            string[] vs = Console.ReadLine().Split();
            string name = vs[0];
            string password = vs[1];
            int money = int.Parse(vs[2]);

            // リストのなかから同じ名前の会社を探す
            Company company = companys.First(x => x.Name == name);

            // パスワードが一致したらお金をおろす
            if (company.Password == password)
                company.Money -= money;
        }

        foreach (Company company in companys)
            Console.WriteLine("{0} {1}", company.Name, company.Money);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

string[] nk = Console.ReadLine().Split();

int N = int.Parse(nk[0]);

int K = int.Parse(nk[1]);

List<Company> companys = new List<Company>();

for (int i=0; i< N; i++)

{

string[] vs = Console.ReadLine().Split();

string name = vs[0];

string password = vs[1];

int money = int.Parse(vs[2]);

companys.Add(new Company(name, password, money));

}

for (int i = 0; i < K; i++)

{

string[] vs = Console.ReadLine().Split();

string name = vs[0];

string password = vs[1];

int money = int.Parse(vs[2]);

// リストのなかから同じ名前の会社を探す

Company company = companys.First(x => x.Name == name);

// パスワードが一致したらお金をおろす

if (company.Password == password)

company.Money -= money;

}

foreach (Company company in companys)

Console.WriteLine("{0} {1}", company.Name, company.Money);

}

完成♪　paizaさん、褒めて褒めて♪

しかしこれでは褒められるどころか雷が落ちます。

結果は50点。

NとKが小さな値であればこれでもよいのですが、大きな値（3685と98373とか、73825と83746）だと処理が5秒以内に終わらず不正解！！

ではどうすればいいのでしょうか？

Dictionaryで時間短縮

リストのなかから同じ名前の会社を探す処理で時間がかかりすぎています。ここはDictionaryを使いましょう。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] nk = Console.ReadLine().Split();
        int N = int.Parse(nk[0]);
        int K = int.Parse(nk[1]);

        Dictionary<string, Company2> pairs = new Dictionary<string, Company2>();
        for (int i=0; i< N; i++)
        {
            string[] vs = Console.ReadLine().Split();
            string name = vs[0];
            string password = vs[1];
            int money = int.Parse(vs[2]);

            pairs.Add(name, new Company2(password, money));
        }

        for (int i = 0; i < K; i++)
        {
            string[] vs = Console.ReadLine().Split();
            string name = vs[0];
            string password = vs[1];
            int money = int.Parse(vs[2]);

            // 同じ名前の会社を探すのだが
            // この部分の処理が飛躍的に速くなっている
            Company2 company2 = pairs[name];

            // パスワードが一致したらお金をおろす
            if (company2.Password == password)
                company2.Money -= money;
        }

        foreach (string name in pairs.Keys)
            Console.WriteLine("{0} {1}", name, pairs[name].Money);
    }

    public class Company2
    {
        public Company2(string password, int money)
        {
            Password = password;
            Money = money;
        }

        public string Password = "";
        public int Money = 0;
    }
}

using System;

using System.Collections.Generic;

class Program

{

static void Main()

{

string[] nk = Console.ReadLine().Split();

int N = int.Parse(nk[0]);

int K = int.Parse(nk[1]);

Dictionary<string, Company2> pairs = new Dictionary<string, Company2>();

for (int i=0; i< N; i++)

{

string[] vs = Console.ReadLine().Split();

string name = vs[0];

string password = vs[1];

int money = int.Parse(vs[2]);

pairs.Add(name, new Company2(password, money));

}

for (int i = 0; i < K; i++)

{

string[] vs = Console.ReadLine().Split();

string name = vs[0];

string password = vs[1];

int money = int.Parse(vs[2]);

// 同じ名前の会社を探すのだが

// この部分の処理が飛躍的に速くなっている

Company2 company2 = pairs[name];

// パスワードが一致したらお金をおろす

if (company2.Password == password)

company2.Money -= money;

}

foreach (string name in pairs.Keys)

Console.WriteLine("{0} {1}", name, pairs[name].Money);

}

public class Company2

{

public Company2(string password, int money)

{

Password = password;

Money = money;

}

public string Password = "";

public int Money = 0;

}

こんどは5秒以内に終わらなかった処理も0.60 秒で終わりました。（N,K）= (3685 98373)なら0.20秒、(73825 83746)なら0.60秒。

問題の趣旨

ダメな方法

Dictionaryで時間短縮

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ