[Algorithm] Codility_GenomicRangeQuery in Java

💡 Codility Medium_GenomicRangeQuery:

문자열에서 P[i]와 Q[i] 사이에 있는 요소 중 가장 영향 계수가 작은 요소 찾기

🌱 코드 in Java

알고리즘: Dynamic Programming

import java.util.*;

class Solution {
       public int[] solution(String S, int[] P, int[] Q) {
        int s_len = S.length(), len = P.length;
        int[][] dp = new int[3][s_len];
        int[] ans = new int[len];
        for (int i = 0; i < s_len; i++) { // 구간 요소별 누적합 구하기
            char c = S.charAt(i);
            int prev = i == 0? 0 : i - 1;
            if (c == 'A') {
                dp[0][i] = dp[0][prev] + 1;
                dp[1][i] = dp[1][prev];
                dp[2][i] = dp[2][prev];
            } else if (c == 'C') {
                dp[0][i] = dp[0][prev];
                dp[1][i] = dp[1][prev] + 1;
                dp[2][i] = dp[2][prev];
            } else if (c == 'G') {
                dp[0][i] = dp[0][prev];
                dp[1][i] = dp[1][prev];
                dp[2][i] = dp[2][prev] + 1;
            } else {
                dp[0][i] = dp[0][prev];
                dp[1][i] = dp[1][prev];
                dp[2][i] = dp[2][prev];
            }
        }
        
        for (int i = 0; i < len; i++) {
            int j = -1;
            while (++j < 3) {
                int comp = P[i] == 0 ? 0 : dp[j][P[i] - 1]; // P가 P[i]가 0이라면 0, P[i] > 0 이라면 시작 지점 이전 값과 비교
                if (comp < dp[j][Q[i]]) // 값이 다르다는 것은 구간 안에 1번이라도 등장한다는 뜻이므로 최소 요소 값부터 확인
                    break;
            }
            ans[i] = j + 1;
        }
        return ans;
    }
}

이 문제는.. 뭔가 DP의 냄새가 나긴 났는데 도저히 누적합을 어떤 식으로 구해야할지 감이 오지 않아서 한참 고민하다가 결국 아이디어를 찾아 떠나게 되었다. 그리고 요소별로 DP를 구하면 되는구나! 하고 깨달아서 위와 같은 코드를 짜게 되었다.

왜 처음에는 이런 방법이 도무지 떠오르지 않는걸까.. 흑흑..
그래도 간만에 DP 문제를 풀어서 재밌었다.

🧠 기억하자

1. 생각하자