[C#] 010 - Score Sum Queries

📄 난이도 : ⭐⭐
📄 언어 : C#

📂문제 링크

---

🔶 풀이

❌ 1．LINQ를 이용하는 방법

• 채점에서 타임오버된 코드. LINQ를 써봤는데 전체를 탐색하는건 비효율적이다.
• 동일한 구조로 for루프로도 풀어봤는데, 수행시간은 똑같이 걸린다.

using System;
using System.Linq;

namespace atCoder.Contest
{
    class Q010_Score_Sum_Queries
    {
        struct Student
        {
            public int I, C, P;
        }

        static void Main()
        {
            int N = Convert.ToInt32(Console.ReadLine());
            Student[] students = new Student[N];

            for (int i = 0; i < N; i++)
            {
                int[] array = Console.ReadLine().Split().Select(Int32.Parse).ToArray();
                students[i].C = array[0];
                students[i].P = array[1];
                students[i].I = i + 1;
            }

            int Q = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < Q; i++)
            {
                int[] queryNum = Console.ReadLine().Split().Select(Int32.Parse).ToArray();
                int L = (
                      from student in students
                      where (student.I >= queryNum[0] && student.I <= queryNum[1]) && student.C == 1
                      select student.P
                       ).Sum();

                int R = (
                      from student in students
                      where (student.I >= queryNum[0] && student.I <= queryNum[1]) && student.C == 2
                      select student.P
                       ).Sum();

                Console.WriteLine($"{L} {R}");
            }
        }
    }
}

⭕ 2．미리 합을 구해두는 방법

• Q를 받을 때 매번 루프를 돌지 않도록 미리 입력단계에서 합계를 구해둔다.
• Q를 받으면 (최대구간의 합 - 최소구간의 합) 으로 합계를 루프없이 구한다.

using System;
using System.Linq;

namespace atCoder.Contest
{
    class Q010_Score_Sum_Queries
    {
        static void Main()
        {
            int N = Convert.ToInt32(Console.ReadLine());

            int[] Lsum = new int[N+1];
            int[] Rsum = new int[N+1];
            for (int i = 1; i < N+1; i++)
            {
                int[] array = Console.ReadLine().Split().Select(Int32.Parse).ToArray();

                Lsum[i] = Lsum[i - 1];
                Rsum[i] = Rsum[i - 1];

                if (array[0] == 1) Lsum[i] += array[1];
                else if (array[0] == 2) Rsum[i] += array[1];
            }

            int Q = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < Q; i++)
            {
                int[] queryNum = Console.ReadLine().Split().Select(Int32.Parse).ToArray();
                int L = Lsum[queryNum[1]] - Lsum[queryNum[0]-1];
                int R = Rsum[queryNum[1]] - Rsum[queryNum[0]-1];

                Console.WriteLine($"{L} {R}");
            }
        }
    }
}

(post-code: 2022-05-05-010)

TOP