Codility Lesson 4 - FrogRiverOne

문제 설명

작은 개구리가 강 반대편으로 가고 싶어 합니다. 개구리는 처음에 강의 한쪽 강둑(위치 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에 떨어집니다. 이것은 강을 가로질러 모든 위치에 나뭇잎이 나타나는 가장 빠른 시간입니다.

함수를 작성합니다:

function solution(X, A);

이 함수는 비어 있지 않은 정수 배열 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] 범위 내의 정수입니다.

문제 접근

1 부터 X 까지의 모든 숫자가 나오는 시점인 index 를 구하라는 것이다.

빈 객체에 1 ~ X 의 값을 모두 미리 저장한다. 그리고 배열을 순회하면서 나온 숫자를 객체에서 하나씩 제거하면서 해당 객체의 모든 숫자가 없어졌을때 index 를 반환하면 된다.

1. 빈 객채에 1 ~ X 에 숫자를 추가한다.
2. 배열 A를 순회하면서 나온숫자를 객체에서 제거시킨다.
3. 해당 객체에 숫자가 없어질때 index 가 정답이다.

function solution(X, A) {
  const info = new Set()

  for (let i = 1; i <= X; i++) {
    info.add(i)
  }

  for (let i = 0; i < A.length; i++) {
    if (info.has(A[i])) {
      info.delete(A[i])
    }

    if (info.size === 0) {
      return i
    }
  }

  return -1
}