[분석] Codility - FrogRiverOne - Javascript

Codility 연습문제 > FrogRiverOne > Javascript
개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 찾는 문제.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

작은 개구리가 강 건너편으로 가고 싶어합니다. 개구리의 처음 강의 둑 (0 위치)에 있고, 반대쪽 (X + 1)에 도달하려고 한다. 그리고 이동을 도와줄 나뭇잎이 강 표면으로 떨어지고 있습니다.

낙엽을 나타내는 N 개의 정수로 구성된 배열 A가 제공됩니다. A[K]는 초 단위로 측정된 시간 K에서 하나의 잎이 떨어지는 위치를 나타냅니다.

목표는 개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 찾는 것입니다. 개구리는 잎이 1에서 X까지 강 건너 모든 위치에 나타날 때만 건널 수 있습니다. 강의 흐름 속도가 무시할 정도로 작다고 가정할 수 있습니다. 즉, 잎이 강에 떨어지면 위치가 바뀌지 않습니다.

1. 낙역의 위치를 요소로 가지고 있는 배열 A가 주어진다.
2. 각 배열의 요소는 초 단위로 측정되어 있다. (1초 ~ )
3. 예를들어, X = 5, A = [1, 3, 1, 4, 2, 3, 5, 4] 이 주어지면 두 번째 6에서는 잎이 위치 5로 떨어집니다. 이것은 잎이 강 건너 모든 위치에 나타나는 가장 빠른 시간입니다.
   
   

[분석]

1. 배열의 길이 및 도달 위치 X는 1 ~ 100,000 범위의 정수이다.
2. 배열 각 요소는 1 ~ X 범위의 정수이다.
3. 개구리가 강 건너편으로 점프할 수 없다면 -1을 반환한다.
4. 강의 1 ~ X 까지 모든 위치에 잎이 있을때만 건널 수 있다.
   
   

[풀이]

1. 배열의 각 index는 초 단위를 나타낸다.
2. 배열의 각 요소의 값은 잎이 떨어진 위치값을 나타낸다.
3. 모든 잎이 즉 1의 간격으로 최종 X까지 채워져 있어야 건널 수 있다.
4. 배열의 각 잎의 위치값이 최종 목표인 X + 1에 해당할 수도 없을 수도 있다.
5. 위치를 중복없이 담을 수 있는 Set 함수를 사용할 수 있다.
6. 결과값뿐만 아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야 합니다.

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

  for (let i = 0; i < A.length; i++) {
    // 잎의 위치를 고유값으로 저장한다.
    position.add(A[i]);

    // 위치의 길이와 X가 같다면 경과시간을 바로 반환한다.
    if (position.size === X) {
      return i;
    };
  }

  return -1;
}

[마치며]

FrogRiverOne 문제는 Set() 함수를 이용해 고유값을 처리할 수 있는 방법으로 해결했습니다. 시간 복잡도는 O(N) 입니다.