[codility] GenomicRangeQuery

GenomicRangeQuery

Find the minimal nucleotide from a range of sequence DNA.

Task Score

62%

Correctness

100%

Performance

0%

---

오늘도 시작은 correctness 100%에 performance 0% ^^~!

제일 작은 문자를 넣어서 숫자로 바꿔주었다. 오늘도 이중포문이 문제인가~ 하고 이중포문을 없애주려고 방법을 바꿔봤다.

 
​x
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        char[] input = S.toCharArray();
        char dna[] = new char[P.length];
        
        for (int i = 0; i < P.length; i++) {
            char temp = 'T';
            
            for (int j = P[i]; j <= Q[i]; j++) {
                
                if (temp > input[j])    temp = input[j];
            }
            
            dna[i] = temp;
        }
        
        int[] result = new int[dna.length];
        
        for (int i = 0; i < dna.length; i++) {
            
            if (dna[i] == 'A')      result[i] = 1;
            else if (dna[i] == 'C') result[i] = 2;
            else if (dna[i] == 'G') result[i] = 3;
            else                    result[i] = 4;
        }
        
        return result;
    }
}

 

하지만 또 correctness 100%에 performance 0% ^^~!

이중포문을 없애려고 했는데 메소드를 쓴게 문제인건지 뭔가 자료구조 문제인 것 같기도 하고 어떻게 고쳐야할지 몰라서 한참을 이렇게바꾸고 저렇게 바꾸고 했다. (자료구조 공부를 좀 해야겠다.. ㅠㅠ)

 
xxxxxxxxxx
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        String[] str = new String[P.length];
        
        for (int i = 0; i < P.length; i++)
            str[i] = S.substring(P[i], Q[i] + 1);
        
        /*System.out.println(Arrays.toString(str));*/
        
        int[] result = new int[P.length];
        
        for (int i = 0; i < P.length; i++) {
            
            if (str[i].indexOf("A") != -1)
                result[i] = 1; 
            else if (str[i].indexOf("C") != -1)
                result[i] = 2; 
            else if (str[i].indexOf("G") != -1)
                result[i] = 3; 
            else
                result[i] = 4; 
        }
        
        return result;
    }
}

 

결국 이방법 저방법 다써보다가 포기하고 다른사람의 100% 코드를 보고 참고(표절)해서 살짝 고친 코드 ㅎㅎ..

여러 사람들의 풀이를 봤는데, 공통점이 이차원 배열을 사용해서 값을 더해 그 값을 비교해주는 식으로 결과값을 찾는 것이었다.

그 중 제일 마음에 드는 방법을 보면서 따라 풀어봤는데, 다른 더 좋은 방법이 있을 것 같은 그런 근거를 모를 생각이 엄청든다.. 나중에 주말이나 하루 푹 쉬는날 날잡고 해봐야겠다.

 

 
xxxxxxxxxx
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int[][] arr = new int[S.length()][4];
        int[] result = new int[P.length];
​
        for (int i = 0; i < S.length(); i++) {
            
            switch (S.charAt(i)) {
                case 'A':
                    arr[i][0] = 1;
                    break;
                case 'C':
                    arr[i][1] = 1;
                    break;
                case 'G':
                    arr[i][2] = 1;
                    break;
                default:
                    arr[i][3] = 1;
                    break;
            }
        }
        
        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++) {
                int sub = 0;
                
                if (P[i] - 1 >= 0)
                    sub = arr[P[i] - 1][j];
                
                if (arr[Q[i]][j] - sub > 0) {
                    result[i] = j + 1;
                    break;
                }
            }
​
        }
        
        return result;
    }
}