FrogRiverOne

/Codility

문제 해석

요약

정수로 구성된 배열이 주어지고, 하나의 정수가 주어진다. 1부터 주어진 정수 값 까지 모두 나온 요소의 인덱스를 구하여라.

전문

🇰🇷 번역

한 작은 개구리가 강의 다른 쪽으로 가고 싶어한다. 그 개구리는 처음에 하나의 강둑(position 0)에 위치하고 있고, 반대편 강둑(position 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초일 때, 나뭇잎은 position 5에 떨어진다. 이것은 나뭇잎이 강 건너 모든 위치에 나뭇잎이 가장 빠른 시간이다.

함수를 작성하시오:
function solution(X, 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는 [2..100,000]범위 안의 정수이다;
  • A의 각 요소는 [1..X]범위 안의 정수이다.

🇺🇸 원문

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

function solution(X, A);

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

  • N and X are integers within the range [1..100,000];
  • each element of array A is an integer within the range [1..X].

🤔 문제 해결 방법 구상

중복은 상관없지만 모든 요소가 다 있어야한다...는 점을 보았을때, set이 가장 먼저 생각났다.

  1. 우선 위치 1부터 X까지 모든 값을 담고있는 Set를 만든다.
  2. 주어진 배열 A의 0번째 요소부터 제거해나간다.
  3. set의 사이즈가 0이 되는 순간 몇 번째인지 리턴한다.
  4. 만약, loop가 종료된 뒤에도 사이즈가 0이 아니라면 -1을 반환한다.

코드 구현

function solution(X, A) {
  const leaves = new Set();
  for (let i = 1; i <= X; i++) {
    leaves.add(i)
  }
  for (let i = 0; i <= A.length; i++) {
    leaves.delete(A[i]);
    if (leaves.size === 0) {
      return i;
    }
  }
  return -1;
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도는 O(n). 공간 복잡도는 O(n)으로 예상한다.

마무리

set에 익숙해지니 너무 편리하다!

Reference & Learn More

MDN Set

Tags
Comments