개발

정수 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/