Codility - Frog River One // C++

문제

 

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:

class Solution { public int solution(int X, int[] 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].

 

개구리는 0의 위치에서 X+1의 위치로 강을 건너서 가고 싶어한다.

 

N의 위치로 점프를 하기 위해서는 1 ~ N-1까지의 나뭇잎이 나무에서 떨어져야 한다.

 

나무에서는 1초마다 나뭇잎이 떨어지는데, M초에 떨어진 나뭇잎의 위치는 A[M]에 저장되어 있다.

 

흐르는 강물의 속도는 고려하지 않을 때(나뭇잎이 떨어지면 그 자리에 가만히 있음), 개구리가 건너가기 위해 나뭇잎이 모두 떨어지는 시간은?

 

못 건넌다면 -1을 return

---

풀이

 

처음엔 단순하게 boolean type의 배열을 선언해서 1~X-1의 배열이 모두 true 값으로 바뀌면 그 때의 시간을 정답으로 return했다.

 

그렇게 하니, O(N^2)의 시간이 나왔고 당연히 실패했다...

 

다음 방법으로는 algorithm header file 내의 find 함수를 이용하여 vector 내에서 1~X-1을 찾아서 가장 큰 index를 return 했는데, O(N)이었지만 find 함수의 시간 때문에 역시 시간 초과가 발생했다.

 

마지막으로 생각해냈던 방법이 map을 이용한 것이었는데, map의 index는 unique한 성질을 가지므로 index 값으로 나뭇잎의 위치를 넣어서 size가 X가 되면 그 때의 vector index를 정답으로 삼았다.

 

map을 이용해도 O(N)이었지만, find를 사용할 때 보다는 훨씬 시간이 단축되어 100%로 통과할 수 있었다.

---

코드

#include <map>

int solution(int X, vector<int> &A) {
    map<int, int> m; // key : leaf location, value : index
    int ans = -1;
    
    for(int i=0;i<A.size();i++){
        m.insert(pair<int,int>(A[i], i));
        
        if(m.size() == X){
            ans = i;
            break;
        }
    }
    
    return ans;
}