개발

DNA 서열은 연속적인 뉴클레오티드의 종류에 대응하여 문자 A ,C, G, T로 구성된 문자열로 나타낼 수 있다.
각 뉴클레오티드는 정수인 'impact factor'를 가지고 있다.
뉴클레오티드 종류 A, C, G, T는 각각 1, 2, 3, 4의 'impact factor'를 가지고 있다.
당신은 다음 몇 가지 쿼리에 답 할 것이다:
주어진 DNA 서열의 특정 부분에 포함 되어있는 뉴클레오티드의 가장 작은 'impact factor'는 무엇인가?

DNA 서열은 N개의 문자로 구성 된 비어있지 않은 문자열 S = S[0]S[1]...S[N-1] 로 주어진다.
각 M개의 정수로 구성된 비어있지 않은 배열 P, Q 안에 M개의 쿼리가 있다.
K번째 쿼리(0 ≤ K < M)는
P[K]와 Q[K] 사이의 DNA 서열이 포함된 뉴클레오티드의 가장 작은 'impact factor'를 찾기를 요구한다.

예를 들어 문자열 S = CAGCCTA 이고 array P, Q 가 다음과 같다면:
    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6

M = 3 쿼리들의 답변들은 다음과 같을 것이다:
- 2와 4 사이의 DNA는 뉴클레오티드 G 와 C(두 번)를 포함하고 있다.
'impact factor'는 각각 3, 2이므로 답변은 2이다.
- 5와 5 사이에는 단일 뉴클레오티드 T를 포함하고, 'impact factor'는 4 이므로 답변은 4 이다.
- 0과 6 사이(전체 문자열)에는 모든 뉴클레오티드를 포함하고,
뉴클레오티드 A의 'impact factor'는 1 이므로 답변은 1 이다.

함수 작성:
class Solution { public int[] solution(String S, int[] P, int[] Q); }

N개의 문자로 구성된 비어있지 않은 문자열 S와 M개의 정수로 구성 된 비어있지 않은 배열 P, Q 두 개가 주어지면
모든 쿼리에 대한 연속적인 답변을 나타내는 M개의 정수로 구성된 배열을 리턴한다.

숫자열은 다음과 같아야 한다:
- 구조체 (C),
- 정수 벡터 (C++),
- 레코드 (Pascal),
- 정수 배열 (그 밖의 다른 프로그래밍 언어).

예를 들어 문자열 S = CAGCCTA 이고 array P, Q 가 다음과 같다면:
    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6
함수는 위에서 설명한 대로 [2, 4, 1]를 리턴해야 한다.

가정 :
- N 은 [1..100,000] 범위의 정수;
- M 은 [1..50,000] 범위의 정수;
- 배열 P, Q의 각 요소는 [0..N − 1] 범위의 정수;
- 0 ≤ K < M라면 P[K] ≤ Q[K];
- 문자열 S는 알파벳 대문자 A, C, G, T로만 구성된다.

복잡도 :
최악의 시간복잡도는 O(N+M);
최악의 공간복잡도는 O(N) (입력 공간 제외)

배열의 요소는 수정할 수 있다.





75%:
https://codility.com/demo/results/trainingSCPXKP-K28/

100% :
https://codility.com/demo/results/trainingFQSN7X-U64/

 함수 작성:
 class Solution { public int solution(int A, int B, int K); }
 정수 A, B, K가 주어지고, 범위 [A..B] 안에서 K로 나누어 떨어지는 정수의 값을 리턴
 즉 : { i : A ≤ i ≤ B, i mod K = 0 }

 예를 들어 A = 6, B = 11, K = 2 면, 함수는 3을 리턴해야 한다.
 왜냐하면 범위 [6..11] 안에 2로 나누어 떨어지는 숫자가 6, 8, 10 3개 있기 때문이다.

 가정:
 A,B는 [0..2,000,000,000] 범위의 정수;
 K는 [1..2,000,000,000] 범위의 정수;
 A ≤ B.

 복잡도:
 최악의 시간복잡도는 O(1);
 최악의 공간복잡도는 O(1);





https://codility.com/demo/results/trainingBTWCPP-XMG/

N개의 정수로 구성된 비어있지 않은 배열 A가 주어진다.
배열 A의 연속된 요소는 길 위의 연속된 자동차를 나타낸다.

배열 A는 0,1 만 포함한다:
- 0 은 자동차가 동쪽으로 이동중임을 나타내고,
- 1 은 자동차가 서쪽으로 이동중임을 나타낸다.

목표는 통과하는 자동차를 세는것이다.
자동차 한 쌍(P,Q)은 0 ≤ P < Q < N이고 P는 동쪽으로 이동하고 Q 는 서쪽으로 이동하며 통과할 때를 말한다.

예를 들어 배열 A가 다음과 같다고 하면:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
우리는 통과하는 차 중에 다섯 쌍을 가지고 있다 : (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

함수 작성:
class Solution { public int solution(int[] A); }
정수 N개의 비어있지 않은 배열 A가 주어지고, 통과하는 차의 쌍 수를 리턴한다.

통과하는 차의 쌍 수가 1,000,000,000를 초과하면 함수는 -1을 리턴해야 한다.

예를들어 다음과 같이 주어진다면:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
위에서 설명한대로 함수는 5를 리턴해야 한다.

가정:
- N은 [1..100,000] 범위의 정수이다.
- 배열 A의 각 요소는 0, 1 중 하나의 값만을 가질 수 있다.

복잡도:
- 최악의 시간복잡도는 O(N);
- 최악의 공간복잡도는 O(1), 입력 값 제외

배열의 요소는 수정할 수 있다.





90%
https://codility.com/demo/results/trainingBN4EAQ-52Q/

100%
https://codility.com/demo/results/trainingVNJ5UB-TCQ/

0으로 초기화 되어있는 N개의 카운터가 주어지고, 두 가지 연산이 있다.
- increase(X) − 카운터 X 를 1 증가시킨다.
- max counter − 모든 카운터를 카운터 최대값으로 설정한다.

M개의 정수로 구성된 비어있지 않은 배열 A가 주어진다. 이 배열은 다음의 연속적인 연산을 나타낸다.
- 만약 A[K] = X 가 1 ≤ X ≤ N 면 연산 K는 increase(X)이고,
- 만약 A[K] = N + 1 이면 연산 K 는 max counter 이다.

예를 들어, N = 5 이고 배열 A가 다음과 같이 주어진다면
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

연속되는 각각의 연산 후에 카운터들의 값은 다음과 같을 것이다.
(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

목표는 모든 연산 후에 모든 카운터의 값을 산출하는 것이다.

함수 작성:
class Solution { public int[] solution(int N, int[] A); }
정수 N과 M개의 정수로 구성된 비어있지 않은 배열 A가 주어지고
카운터들의 값을 나타낸 연속된 정수를 리턴한다.

수열은 다음과 같아야 한다:
- 구조체 (C),
- 정수 벡터 (C++),
- 레코드 (Pascal),
- 정수 배열 (그 밖의 다른 프로그래밍 언어).

예를들어 다음과 같이 주어진다면
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

위에서 설명한대로 함수는 [3, 2, 2, 4, 2]를 리턴해야 한다.

가정:
N 과 M은 [1..100,000] 범위의 정수이다.
배열 A의 각 요소는 [1..N + 1] 범위의 정수이다.

복잡도:
최악의 시간복잡도는 O(N+M);
최악의 공간복잡도는 O(N), 입력 공간 제외.

입력된 배열의 요소는 수정 될 수 있다.

88%
https://codility.com/demo/results/trainingUKVD8F-3R7/

100%
https://codility.com/demo/results/trainingFVZK33-75M/

 함수 작성:
 class Solution { public int solution(int[] A); }
 N개의 정수로 구성된 배열 A가 주어지고, A에 없는 가장 작은 양수 (0보다 큰)를 리턴한다.

 예를들어
 A[0] = 1
 A[1] = 3
 A[2] = 6
 A[3] = 4
 A[4] = 1
 A[5] = 2
 가 주어지면 함수는 5를 리턴해야 한다.

 가정:
 N 은 [1..100,000] 범위의 정수
 배열 A의 각 요소는  [−2,147,483,648..2,147,483,647] 범위의 정수

 복잡도:
 최악의 시간복잡도는 O(N);
 최악의 공간복잡도는 O(N) (입력 공간 제외)
 배열의 요소들은 수정될 수 있다.






https://codility.com/demo/results/trainingR78BM7-68F/