1 minute read

[Lesson5] Prefix Sums

GenomicRangeQuery : Find the minimal nucleotide from a range of sequence DNA.


Java Solution

Task Score : 62

Correctness : 100 Performance : 0

import java.util.*;

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        HashMap<Character, Integer> dna = new HashMap<Character, Integer>();
        dna.put('A', 1);
        dna.put('C', 2);
        dna.put('G', 3);
        dna.put('T', 4);

        int[] result = new int[P.length];
        for(int i = 0; i < P.length; i++){
            int min = 4;
            for(int j = P[i]; j <= Q[i]; j++){
                char n = S.charAt(j);
                int seq = dna.get(n);
                if(min > seq){
                    min = seq;    
                }
            }
            result[i] = min;
        }
        return result;
    }
}

Task Score : 100

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        // A, C, G 배열을 이용하여 String에서 나온 횟수를 저장
        int[] A = new int[S.length()+1];
        int[] C = new int[S.length()+1];
        int[] G = new int[S.length()+1];
        int a = 0;
        int c = 0;
        int g = 0;

        for(int i = 0; i < S.length(); i++){
            switch(S.charAt(i)){
                case 'A':
                    a++;
                case 'C':
                    c++;
                case 'G':
                    g++;
            }
            A[i+1] = a;
            C[i+1] = c;
            G[i+1] = g;
        }
        // P[K]와 Q[K]사이의 변화된 수 확인하여 result에 넣기
        int[] result = new int[P.length];
        for(int i = 0; i < P.length; i++){
            int p = P[i];
            int q = Q[i]+1;
            if(A[p] < A[q]){
                result[i] = 1;
            }else if(C[p] < C[q]){
                result[i] = 2;    
            }else if(G[p] < G[q]){
                result[i] = 3;
            }else{
                result[i] = 4;    
            }
        }
        return result;
    }
}

PHP Solution

function solution($S, $P, $Q) {
    $A = array_fill(0, strlen($S)+1, 0);
    $C = array_fill(0, strlen($S)+1, 0);
    $G = array_fill(0, strlen($S)+1, 0);
    $a = 0;
    $c = 0;
    $g = 0;

    for($i = 0; $i < strlen($S); $i++){
        switch($S{$i}){
            case 'A':
                $a++;
            case 'C':
                $c++;
            case 'G':
                $g++;
        }    
        $A[$i+1] = $a;
        $C[$i+1] = $c;
        $G[$i+1] = $g;
    }
    $result = array();
    for($i = 0; $i < count($P); $i++){
        $p = $P[$i];
        $q = $Q[$i]+1;
        if($A[$p] < $A[$q]){
            $result[$i] = 1;
        }else if($C[$p] < $C[$q]){
            $result[$i] = 2;
        }else if($G[$p] < $G[$q]){
            $result[$i] = 3;    
        }else{
            $result[$i] = 4;    
        }
    }
    return $result;
}