Codility - FrogRiverOne 풀이

Lesson4. FrogRiverOne

안녕하세요!

오늘은 Lesson4의 두 번째 문제인 FrogRiverOne에 대해 풀이해보려 합니다.

Question

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

FrogRiverOne coding task - Learn to Code - Codility

 

개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 찾아야 합니다.

목적지를 나타내는 X와 각 요소의 범위가 1 ~ X로 이루어진 배열 A가 주어지는데, 배열 A를 탐색하며 1부터 X 까지의 수가 모두 나타났을 때의 index를 반환하면 됩니다.

 

만약 X가 5, A가 [1, 3, 1, 4, 2, 3, 5, 4] 라고 했을 때, 1부터 5까지의 수가 모두 나타난 배열 A의 index는 6이므로 6을 반환하면 되고, 혹시나 나타나지 않았을 경우에는 -1을 반환하면 됩니다.

Answer

이번에는 자료구조 중 하나인 Set을 활용하여 풀이해보았습니다!

* Set은 중복된 value를 저장하지 않습니다.

 

1. 새로운 Set 변수 s를 생성합니다.

2. A 배열의 루프를 돌며, s에 값( A[idx] )을 추가합니다. 

3. 만약 s의 길이가 X와 같다면, 1 부터 X 까지의 수가 모두 채워졌다는 의미이므로 해당 index를 반환합니다.

    -> 배열 A 내의 요소의 범위가 1 ~ X라는 전제가 깔려있기 때문에 가능한 로직입니다!

4. 루프를 돌고 난 뒤에도 index가 반환되지 않았을 경우에는 -1을 최종적으로 반환합니다.

 

풀이 코드는 아래와 같습니다. ( 시간 복잡도는 O(N) )

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

 

풀이 결과

The End

문제를 이해하고 난 후엔 그리 어렵지 않게 풀 수 있었던 것 같습니다.

다음 시간에는 Lesson4의 세 번째 문제인 MaxCounters에 대해 풀이해보려 합니다.

봐주셔서 감사합니다!