[Codility] Lesson4 - Counting Elements: Frog River One (c++)

Problem

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].

How to solve

- 정보

개구리의 처음 위치 0

개구리는 강을 건너려고하고, X+1 로 이동을 원함

강을 건너는 동안 나뭇잎이 강으로 떨어짐

 

배열 A, 낙엽을 나타내는 N개의 정수로 구성된 배열

A[K], time K에 나뭇잎이 떨어지는 위치

 

 

- 구해야 하는것?

개구리가 강의 다른 쪽으로 건널 수 있는 최소 시간 구하기 

개구리가 강을 건널 수 없다면 return -1

 

즉,

배열 A에 1~X까지의 숫자가 N개 주어지는데,

X까지의 숫자가 한번씩 다 나오는 최소 index return 하는 문제이다 

 

- 풀이

배열을 순환하며 정수를 check 하고, 새롭게 나온 정수의 갯수를 cnt에 저장

 

A 배열을 순환하면서 새로운 숫자가 나올 때 체크 벡터에 check 후 cnt+=1

cnt=X 인 경우, 1~X의 모든 정수가 한번 씩 다 나온 것이니 그때의 idx return 

다 돌았는데, cnt !=X 라면 안나온 정수가 있는 것이니 -1 return

 

첫 풀이에서 원소가 1개일 때 통과가 되지 않았다 ㅠㅠ원소 1개인 경우에 대한 조건을 추가해주었다(배열의 갯수가 0,1 일때의 조건을 주의하자)app.codility.com/demo/results/training9G6P9Q-6BK/

Solution(c++)

#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int X, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    int cnt = 0;
    vector<int> v(len, 0);
    //원소가 1개 인 경우
    if(len == 1){
        if(A[0] == X){
            return 0;
        }
        else{
            return -1;
        }
    }
    for(int i=0; i<len; i++){
        if(v[A[i]] == 0){
            // 한번도 나온적이 없다면
            v[A[i]] = 1;
            cnt += 1;
            if(cnt == X){
                return i;
            }
        }
    }
    if(cnt != X){
        return -1;
    }
}

Test Result

app.codility.com/demo/results/trainingH34YDH-M2K/

Test results - Codility