Codility Prefix Sums : GenomicRangeQuery Java (코딜리티 자바, Prefix sum 개념을 알자)

오랜만에 풀었다.. 열심히 풀려고 했는데..

Lesson 5 Prefix Sums - GenomicRangeQuery Find the minimal nucleotide from a range of sequence DNA. 아 이 문제 정말 짜증 났다.

우선 문제를 살펴보면, S = CAGCCTA 와 같은 DNA 시퀀스와 배열 P, Q가 주어진다. S는 A, C, G, T 문자로 구성되어 있는데, 각각 1, 2, 3, 4의 값을 갖는다.

문제는 문자열 S의 P[i] ~ Q[i] DNA 중 가장 작은 값을 리턴하는 것이다. 무슨 말인지 이해하기 어려울 땐 문제에서 주어진 예를 봐야 한다.

S = CAGCCTA, P = [2, 5, 0], Q = [4, 5, 6]가 주어졌을 때, S의 2~4 범위에 해당하는 GCC 중 작은 값인 2(=C)가 리턴 배열의 첫 번째 원소가 되고, 0~6의 범위에 해당하는 CAGCCTA 중 가장 작은 값인 1(=A)가 리턴 배열의 마지막 원소가 되는 것이다. ...