[코딜리티/Java] GenomicRangeQuery

A, C, G, T (각 1, 2, 3, 4 impact factor로 매핑되는)로 이루어진 String s과 s의 시작 종료 구간 값을 갖는 P[N], Q[N] 배열을 입력받아 각 구간 별로 가장 작은 impact factor를 갖는 배열을 반환하는 문제.

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 1);
        map.put('C', 2);
        map.put('G', 3);
        map.put('T', 4);
        int[] result = new int[P.length];
        char[] chars = S.toCharArray();
        for (int i = 0; i < P.length; i++) {
            int maxVal = Integer.MAX_VALUE;
            for (int j = P[i]; j <= Q[i]; j++) {
                // 최소값 판단
                maxVal = Math.min(maxVal, chars[j]);
            }
            result[i] = maxVal;
        }
        for (int i = 0; i < result.length; i++) {
            result[i] = map.get((char)result[i]);
        }
        return result;
    }
}

처음에는 매번 다 구간별로 loop돌면서 최소값을 찾는 식으로 했으나 모두 timeout이 발생하였다.

그래서 아래와 같이 구현 방식을 변경하였다.

최초에 String s를 다 돌면서 각 요소들이 몇 개 있는지 모두 카운트해놓고, 구간 별 계산 시 서로의 차이값을 확인해서 최소 impact factor를 구하는 것이다. 한 번 카운트를 다 해놨기 때문에 최소 impact factor를 구할 때 loop를 반복할 필요가 없고, 단순히 2일 때의 count배열과 4일 때의 count배열의 차이만 구하면 된다. 

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int[] result = new int[P.length];
        int[][] count = new int[S.length()+1][4];
        // 초기화
        count[0] = new int[] {0, 0, 0, 0};
        for (int i = 1; i < count.length; i++) {
            sumArray(count[i], count[i-1]);
            char c = S.charAt(i-1);
            // 카운트를 하고
            if (c == 'A') {
                count[i][0]++;
            } else if (c == 'C') {
                count[i][1]++;
            } else if (c == 'G') {
                count[i][2]++;
            } else if (c == 'T') {
                count[i][3]++;
            }
        }

	// P와 Q loop하면서 
        for (int i = 0; i < P.length; i++) {
            int[] subCountOne = count[P[i]];
            int[] subCountTwo = count[Q[i] + 1];
            // 차이값을 계산하고
            int[] minus = minusArray(subCountOne, subCountTwo);
            // 최소 impact factor를 추출
            result[i] = getMin(minus);
        }

        return result;
    }

    private void sumArray(int[] curr, int[] prev) {
        for (int i = 0; i < curr.length; i++) {
            curr[i] += prev[i];
        }
    }

    private int[] minusArray(int[] subCountOne, int[] subCountTwo) {
        int[] result = new int[subCountOne.length];
        for (int i = 0; i < subCountOne.length; i++) {
            result[i] = subCountTwo[i] - subCountOne[i];
        }
        return result;
    }

    private int getMin(int[] minus) {
        for (int i = 0; i < minus.length; i++) {
            if (minus[i] > 0) {
                return i + 1;
            }
        }
        return 0;
    }
}