[Codility] Lesson 6- GenomicRangeQuery

안풀어봤던 유형이라서 그런건지, 정말 너무너무너무너무너뭠눰눠무머누 헤맸다 ㅠㅠㅠ 

가장 직관적인 방법인 for 이중루프는 당연히 O(n*m) 으로 실패다! 

따라서, Counting Sort 개념을 살짝 가져와야하는데,

n번째 글자에서 m번째 글자 사이의 최솟값은, 

m번째 까지 각 글자의 카운팅 - n-1번째 까지의 각 글자의 카운팅 

의 결과를 구하고 그 카운팅이 0이 아닌 최초의 값이 최솟값이 된다.

말로하니까 어려운데,

"ACTTTCAG" 에서 2번째와 5번째사이의 최솟값을 구하려고 하면

counting[2] = {1,1,0,1} , counting[1]={1,1,0,0}

counting[5]={1.2,0,3} 이니까 그 사이의 최솟값은 

counting[5] - counting[1] = {0,1,0,3} 

이니까 0이아닌 최초의 인덱스 "1(C)" (실제 정답은 +1인 2) 이 정답이다.

이것저것 신경쓸 것도 많고, 깔끔하지도 못한 코드다 ㅠ____ㅠ

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int[][] counting=new int[S.length()][4];
	int[] result=new int[P.length];
		//[A][C][G][T] 의 카운팅을 각 인덱스를 거칠 때마다
		//즉,counting[1]=1번째 인덱스를 거쳤을 때 카운팅

		//"AACTG"
		switch(S.charAt(0)){		
			case 'A':
				counting[0][0]++;
				break;
			case 'C':
				counting[0][1]++;
				break;
			case 'G':
				counting[0][2]++;
				break;
			case 'T':
				counting[0][3]++;
		}
		
		for(int i=1; i<S.length(); i++){
			for(int j=0; j<4; j++)
				counting[i][j]=counting[i-1][j];
			switch(S.charAt(i)){		
			case 'A':
				counting[i][0]++;
				break;
			case 'C':
				counting[i][1]++;
				break;
			case 'G':
				counting[i][2]++;
				break;
			case 'T':
				counting[i][3]++;
			}
		}

		
		//A, C, G and T
		for(int i=0; i<P.length; i++){
			int[] countingArray=new int[4];
			int min=-1;
			if(P[i]==0){
			    countingArray=counting[Q[i]];
			    for(int j=0; j<4; j++){
			    	if(countingArray[j]> 0) {
				    	min=j+1;
				    	break;
			   	    }
			    }
			}
			
			else{
		    	for(int j=0; j<4; j++){
			        countingArray[j]=counting[Q[i]][j]-counting[P[i]-1][j];
				    if(countingArray[j]> 0) {
				    	min=j+1;
					    break;
			    	}
			    }
			}
			result[i]=min;
			
	    }
	    return result;
    }
}

히유 힘들로