개발

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/

정수 N개로 구성된 비어있지 않은 배열 A가 주어진다.

permutation이란 1부터 N까지 각 요소를 단 한 번만 포함하는 숫자들이다.

예를들어 배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

permutation이다. 하지만 배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

permutation이 아니다. 왜냐하면 2가 빠졌기 때문이다.

목표는 배열 A가 permutation인지 아닌지 확인하는 것이다.

함수 작성:

class Solution { public int solution(int[] A); }

배열 A가 주어지고, 배열 A가 permutation이라면 1을 리턴 아니면 0을 리턴한다.

예를들어 배열 A가 다음과 같다면

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

함수는 1을 리턴해야한다.

배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

함수는 0을 리턴해야한다.

가정:

N은 [1..100,000] 범위의 정수이다.

배열 A의 각 요소는 [1..1,000,000,000] 범위의 정수이다.

복잡도:

최악의 시간복잡도는 O(N);

최악의 공간복잡도는 O(N) (입력공간 제외)

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

https://codility.com/demo/results/trainingWXN3W6-5WB/

작은 개구리는 강의 반대편으로 가고 싶어 한다.

개구리는 처음에 강 둑 한 곳(위치 0)에 위치해 있고 반대쪽 둑(위치 X+1)으로 가고 싶어 한다.

잎들은 나무에서 강 표면으로 떨어진다.

떨어진 잎을 표현하는 N 개의 정수로 이루어진 배열 A가 주어진다.

A[K]는 K초에 떨어지는 잎의 위치를 표시한다.

목표는 개구리가 강의 반대편으로 점프할 수 있는 가장 빠른 시간을 찾는것이다.

개구리는 1부터 X 위치 까지 강을 건너는 동안 잎이 나타날 때만 이동할 수 있다.

(우리는 잎이 있는 위치만으로 1부터 X까지 이동하는 가장 빠른 시간을 찾기 원한다는 것이다.)

강에 있는 동안의 속도는 무시할 만큼 작다고 가정할 것이다.

즉 잎은 강에 떨어진 후에 위치가 변하지 않는다.

예를 들어 정수 X = 5 이고 배열 A가 다음과 같다면

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

6초에 잎이 위치 5에 떨어진다.

이것이 잎이 강을 가로 지르는 모든 위치에 나타나는 가장 빠른 시간이다.

함수 작성:

class Solution { public int solution(int X, int[] A); }

N개의 정수로 구성된 비어있지 않은 배열 A와 정수X가 주어지면

개구리가 강의 반대편으로 점프할 수 있는 가장 작은 시간을 리턴한다.

만약 개구리가 강의 반대편으로 점프할 수 없다면, 함수는 -1을 리턴해야 한다.

예를들어 정수 X = 5 이고 배열 A가 다음과 같다면

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

위에서 설명한 것처럼 함수는 6을 리턴해야한다.

가정 :

N 과 X는 [1..100,000] 범위의 정수;

A의 모든 요소는 [1..X] 범위의 정수이다.

복잡도 :

최악의 시간복잡도는 O(N);

최악의 공간복잡도는 O(X) (입력 공간 제외)

배열의 모든 요소는 수정 가능하다.

https://codility.com/demo/results/training9GNH47-G8Z/

배열 A는 N개의 각기 다른 정수로 구성된다.
배열은 [1..(N + 1)] 범위의 정수를 포함하며, 단 하나의 요소만 빠져있다. 목표는 빠진 요소를 찾는 것이다.

함수 작성 :
class Solution { public int solution(int[] A); }
배열 A를 받아서, 빠진 요소를 리턴한다.

예를 들어 배열 A 가 다음과 같다면:
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
함수는 빠진 요소인 4를 리턴 할 것이다.

가정 :
N은 [0..100,000] 범위의 정수;
A의 요소는 모두 다르다.
A의 각 요소는 [1..(N + 1)] 범위의 정수이다.

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





https://codility.com/demo/results/trainingB3DXRP-WUF/

비어있지 않은 배열 A는 N개의 정수로 구성되어 있다. 배열 A는 테잎의 숫자들을 나타낸다.

 0 < P < N 인 정수 P는 테잎을 비어있지 않은 두 파트로 나눈다:
 A[0], A[1], ..., A[P − 1], A[P], A[P + 1], ..., A[N − 1].

 두 파트간의 차이 값을 구하는 식은 :
 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

 다시 말하면, 첫 파트의 합계와 두번째 파트의 합계 차이값의 절대값이다.

 예를 들어 다음과 같은 배열 A가 있다면:
 A[0] = 3
 A[1] = 1
 A[2] = 2
 A[3] = 4
 A[4] = 3

 4가지 방법으로 나눌 수 있다.:
 P = 1, 차이 = |3 − 10| = 7
 P = 2, 차이 = |4 − 9| = 5
 P = 3, 차이 = |6 − 7| = 1
 P = 4, 차이 = |10 − 3| = 7

 함수 작성:
 int solution(int A[], int N);

 N 개의 정수로 구성된 비어있지 않은 배열 A, 차이값의 최소값을 리턴한다.

 예를 들어
 A[0] = 3
 A[1] = 1
 A[2] = 2
 A[3] = 4
 A[4] = 3
 가 주어진다면, 상술 한 바와 같이 함수는 1을 리턴하게 된다.

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

 복잡도 :
 최악의 시간복잡도는 O(N)
 최악의 공간복잡도는 O(N) (입력값을 위한 공간 제외)
 배열의 요소는 수정 가능하다.

https://codility.com/demo/results/trainingVW44CT-URM/

작은 개구리는 길을 건너고 싶어한다. 개구리는 현재 X 위치에 있고 Y 보다 같거나 큰 위치로 이동하길 원한다. 개구리는 항상 고정된 D 거리 만큼을 점프한다.

작은 개구리가 목적을 달성할 수 있는 가장 작은 점프 횟수를 구해라.

함수는 X, Y, D 세 개의 int 파라미터가 주어지고, X에서 Y보다 같거나 큰 위치로 이동시 가장 작은 점프 횟수를 리턴하도록 작성

예를 들어
 X = 10
 Y = 85
 D = 30
 가 주어진다면 개구리가 아래처럼 이동하기 때문에 리턴은 3이다.
 첫 점프 후 위치는     10 + 30 = 40
 두 번째 점프 후 위치는   10 + 30 + 30 = 70
 세 번째 점프 후 위치는  10 + 30 + 30 + 30 = 100

 가정 :
 X, Y, D 는 [1..1,000,000,000] 범위의 정수;
 X ≤ Y.

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

https://codility.com/demo/results/trainingWDWBJC-B3J/