boraBong

💬 문제 https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ 처음엔 굉장히 간단한 문제라 생각했지만, 효율성 테스트를 통과하지 못해 굉장히 애를 썼다. O(N^2)의 효율성을 → O(N + M)으로 높이기 위해 구간합을 사용해주었다. 💬 Idea a, c, g, t 각각의 배열을 만들어 (t는 없어도 됨) 알파벳이 나온 구간에는 이전 값 + 1을 해주어 저장해준다. 이후 P를 돌면서 (P) 에서 (Q + 1) 까지의 차가 0 이상일 때 a,c,g,t 중 조건에 해당하는 값을 ans에 append한다. Q + 1 까지인이유: 이전 인덱스와 비교하여 해당 구간에서 알파벳이 등장했는지를 파악하기 위해 배열의 인덱스를 +..