코딩 테스트 - GenomicRangeQuery

18일 치를 풀려다가 문제 이해가 어려워서 번역기를 돌려보았다 ↓

DNA 서열은 문자 A , C , G 및 T 로 구성된 문자열로 표시될 수 있으며 , 이는 서열의 연속적인 뉴클레오티드 유형에 해당합니다. 각 뉴클레오타이드에는 임팩트 팩터 가 있으며 이는 정수입니다. 유형 A , C , G 및 T 의 뉴클레오티드는 각각 1, 2, 3 및 4의 충격 계수를 갖는다. 다음과 같은 몇 가지 질문에 답할 것입니다. 주어진 DNA 서열의 특정 부분에 포함된 뉴클레오티드의 최소 영향 인자는 무엇입니까?

문제를 읽은 나의 마음 : 무슨 말을 하는 걸까? ^^

-> 영어 공부를 한참 한 뒤 -> 풀어봄

-> large random이 망했다!

이렇게 된 이상 남의 코드를 검색해 보자...

해서 나온 코드

package codility;

public class GenomicRangeQuery_221218 {

    public static void main(String[] args) {

       

        String s = "CAGCCCTA";

        int [] P = {2,5,0};

        int [] Q = {4,5,6};

        solution(s, P, Q);

    }  

    public static int[] solution(String S, int[] P, int[] Q) {

       

        //A C G T

        //1 2 3 4

        //2  5  0

        //4  5  6

        //아하 문자열의 2~4까지 중에 작은 ACGT를 찾으면 되는 거군

        int [][] arr = new int[S.length()][4];

        int [] answer = new int[P.length];

        char tempC = 'T';

        int temp = 0;

        for(int i = 0; i < S.length(); i++){    

            tempC = S.charAt(i);

            if(tempC == 'A'){

                arr[i][0] = 1;

            }else if(tempC == 'C'){

                arr[i][1] = 1;

            }else if(tempC == 'G'){

                arr[i][2] = 1;

            }else{

                //T

                arr[i][3] = 1;

            }

        }

        for(int i = 1; i < S.length(); i++){

            for(int j = 0; j < 4; j++){

                arr[i][j] += arr[i-1][j];

            }

        }

        for(int i = 0; i < P.length; i++){

            for(int j = 0; j < 4; j++){

                temp = 0;

                if(P[i] - 1 >= 0){

                    temp = arr[P[i]-1][j];

                    System.out.println(temp + "값");

                }

                if(arr[Q[i]][j] - temp > 0){

                    answer[i] = j+1;

                    break;

                }

            }

        }

        for(int i : answer){

            System.out.printf(i + " ");

        }

        System.out.println();

        return answer;

    }

}

2차원 배열을 쓰고 for문을 막 이중으로 써도 O(N+M)이라니...

(사실 나는 3중 for문에 1차원 배열 2개를 썼다!)

효율의 세계는 재미있는 것