C#初心者がAランク(相当)問題に挑戦！Listからただの配列に変更しタイムアウトを解消した

何の記事？

• 最近、急に仕事でC#を使うようになったので、腕試しにpaizaのAランク相当の問題に挑戦しました。
• 提出したコードがタイムアウトになり、この問題を解決した方法を共有します。

当記事の著者のレベル

• C#歴は3ヶ月です。
• 元々は、C / C++を主に使っていました。

挑戦した問題

• paizaのAランク相当の問題「本の整理」です。
• 問題文は、下記リンク先を参照ください。

作成したコードその1

• 本の一覧をListに格納したところ、テスト10で、タイムオーバーでの失敗となりました。
  • 実行時間は、5.00 秒と表示されました。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int bookNum = int.Parse(Console.ReadLine());
        string[] strBooks = Console.ReadLine().Split(' ');
        List<int> books = new List<int>();
        foreach(var b in strBooks)
        {
            books.Add(int.Parse(b));
        }
        
        int chgCount = 0;
        for(int i=0; i<bookNum-1; i++){
            int min = books[i];
            int minId = i;
            for(int j=i+1; j<bookNum; j++){
                if(min > books[j]){
                    min = books[j];
                    minId = j;
                }
            }
            if(minId > i){
                books[minId] = books[i];
                books[i] = min;
                chgCount++;
            }
        }
        
        Console.WriteLine(chgCount);
    }
}

作成したコードその2

• その1でのタイムオーバーを解消するため、本の一覧をListではなく、ただの配列に変更したところ、テスト10をパスしました。
  • 実行時間は、4.88 秒と表示されました。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int bookNum = int.Parse(Console.ReadLine());
        string[] strBooks = Console.ReadLine().Split(' ');
        int[] books = new int[bookNum];
        for(int i=0; i<bookNum; i++)
        {
            books[i] = int.Parse(strBooks[i]);
        }
        
        int chgCount = 0;
        for(int i=0; i<bookNum-1; i++){
            int min = books[i];
            int minId = i;
            for(int j=i+1; j<bookNum; j++){
                if(min > books[j]){
                    min = books[j];
                    minId = j;
                }
            }
            if(minId > i){
                books[minId] = books[i];
                books[i] = min;
                chgCount++;
            }
        }
        
        Console.WriteLine(chgCount);
    }
}

まとめ

• 複数要素をもつデータ型として、Listからただの配列に変更すると、タイムオーバーを解消できました。
• Listに比べて実行時間が小さいという利点があるので、要素数が固定の場合は、Listではなくただの配列を使用すると良いです。
• より実行時間を小さくするには、探索のアルゴリズムを現在使用している線形探索から二分探索などよりに変更すると良さそうです。

2024/7/30 追記

• paizaの実行環境のページにC#のTime limitは、5.0 secondsと書かれていました。実行時間が5.0 secondsでタイムアウトと判定されたこと、及び5.0 seconds未満の実行時間でタイムアウトが解消した結果と一致しています。

2024/7/31 追記

• LINQを多用してコードを作成しまたところ、コードの行数が少なくなりすっきりしましたが、テスト10のみタイムオーバーとなってしまいました。

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

class Program
{
    static void Main()
    {
        int bookNum = int.Parse(Console.ReadLine());
        int[] books = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        
        int chgCount = 0;
        for(int i=0; i<bookNum-1; i++){
            int min = books.Skip(i).Take(bookNum-i).ToArray().Min();
            int minId = Array.IndexOf(books, min);
            if(minId > i){
                books[minId] = books[i];
                books[i] = min;
                chgCount++;
            }
        }
        
        Console.WriteLine(chgCount);
    }
}