Lesson4. Counting Elements - FrogRiverOne

FrogRiverOne - Find the earliest time when a frog can jump to the other side of a river.

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

문제요약

정수 배열 A에서 1부터 X까지 모두 등장하는 index를 반환, 없으면 -1반환

Assume that:

N and X are integers within the range [1..100,000];

each element of array A is an integer within the range [1..X].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(X) (not counting the storage required for input arguments).

풀이

A를 순서대로 확인하면서 1부터 X까지 나타나는 첫 index를 저장. 전체를 다 처리하고 나면 해당 index들 중 가장 마지막 index를 반환. 등장하지 않는 경우가 있으면 -1반환