GenomicRangeQuery (누적합)

DNA 서열은 문자 'A', 'C', 'G', 'T'로 표현되며, 각 뉴클레오타이드는 다음 영향도(정수)를 가진다:
A → 1
C → 2
G → 3
T → 4

여러 개의 구간 질의가 주어졌을 때, 각 질의 [P[K], Q[K]] (양끝 포함) 구간 안에 포함된
뉴클레오타이드의 "최소 영향도"를 구하라.

입력:
문자열 S = S[0]S[1]...S[N-1], N = |S| (1 ≤ N ≤ 100,000), 문자들은 오직 'A','C','G','T'
정수 배열 P, Q (각 길이 M, 1 ≤ M ≤ 50,000), 각 원소는 0 ≤ P[K] ≤ Q[K] ≤ N-1

출력:
각 질의 K(0 ≤ K < M)에 대해, S의 부분 문자열 S[P[K]..Q[K]]에 존재하는 뉴클레오타이드들의
최소 영향도를 정수로 구해, 길이 M의 결과 배열로 반환

예시:
S = "CAGCCTA"
P = [2, 5, 0]
Q = [4, 5, 6]

질의별 해석:
[2,4] 구간의 문자: "G","C","C" → 영향도 {3,2,2} → 최소 2
[5,5] 구간의 문자: "T" → 영향도 4
[0,6] 구간의 문자: 전체 "CAGCCTA" → 'A'(1) 존재 → 최소 1
결과: [2, 4, 1]

요구사항:
효율적인 알고리즘 구현 (대규모 N, M에서 동작해야 함)

public class GenomicRangeQuery
{
    public enum DNA
    {
        A = 1,
        C = 2,
        G = 3,
        T = 4
    }
 
    public int[] solution(string S, int[] P, int[] Q)
    {
        // 누적합은 0부터 시작하는게 편하기 때문에, 길이를 하나 더 늘림
        Dictionary<DNA, int[]> dnaCountDic = new Dictionary<DNA, int[]>()
        {
            { DNA.A, new int[S.Length + 1] },
            { DNA.C, new int[S.Length + 1] },
            { DNA.G, new int[S.Length + 1] },
            { DNA.T, new int[S.Length + 1] }
        };
 
        int[] result = new int[P.Length];
 
        for (int i = 0; i < S.Length; i++)
        {
            char character = S[i];
 
            // 직전 누적 복사
            dnaCountDic[DNA.A][i + 1] = dnaCountDic[DNA.A][i];
            dnaCountDic[DNA.C][i + 1] = dnaCountDic[DNA.C][i];
            dnaCountDic[DNA.G][i + 1] = dnaCountDic[DNA.G][i];
            dnaCountDic[DNA.T][i + 1] = dnaCountDic[DNA.T][i];
 
            // 현재 문자 반영
            switch (character)
            {
                case 'A': 
                    dnaCountDic[DNA.A][i + 1]++; 
                    break;
 
                case 'C':
                    dnaCountDic[DNA.C][i + 1]++; 
                    break;
 
                case 'G': 
                    dnaCountDic[DNA.G][i + 1]++; 
                    break;
 
                case 'T': 
                    dnaCountDic[DNA.T][i + 1]++; 
                    break;
            }
        }
 
        for (int i = 0; i < P.Length; i++)
        {
            int startIndex = P[i];
            int endIndex = Q[i] + 1; // 누적합 배열은 0부터 시작하기 때문에 +1
 
            if (dnaCountDic[DNA.A][endIndex] - dnaCountDic[DNA.A][startIndex] > 0)
            {
                result[i] = (int)DNA.A;
            }
            else if (dnaCountDic[DNA.C][endIndex] - dnaCountDic[DNA.C][startIndex] > 0)
            {
                result[i] = (int)DNA.C;
            }
            else if (dnaCountDic[DNA.G][endIndex] - dnaCountDic[DNA.G][startIndex] > 0)
            {
                result[i] = (int)DNA.G;
            }
            else
            {
                result[i] = (int)DNA.T;
            }
        }
 
 
        return result;
    }
 
}