[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} 이..
이론/문제풀이
2018. 8. 12.