[Codility] Lesson 4 : FrogRiverOne - JAVA

문제

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].
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int X, int[] A)에 입력되는 X 값의 범위는 1 ~ 100,000이고,
배열 A는 1부터 X까지의 요소를 가질 수 있다.

개구리가 X+1만큼 떨어져 있는 강 반대편으로 가고 싶어한다.
(참고로 개구리의 처음 위치는 0이다.)
배열 A에는 나뭇잎이 떨어지는 위치가 저장되어 있으며, 개구리는 위치 1만큼밖에 점프하지 못한다.

예를 들어 배열 A에 다음과 같이 되어있다고 한다면
        A[0] = 1
        A[1] = 3
        A[2] = 1
        A[3] = 4
        A[4] = 2
        A[5] = 3
        A[6] = 5
        A[7] = 4

0초에는 위치 1에 나뭇잎이 떨어지고 1초에는 위치 3에 나뭇잎이 떨어진다.
이렇게 배열을 반복하다 보면 1, 2, 3, 4, 5 위치에 모두 나뭇잎이 떨어지는 경우가 있는데
이 때의 시간을 계산해 반환하면 된다.
예시로 작성한 배열 A에는 index 6에서 1, 2, 3, 4, 5 위치에 모두 나뭇잎이 떨어지게 되므로
6을 반환해주면 된다.

그러나 배열을 모두 확인해도 강을 건널 수 없는 경우에는 -1 값을 반환해주면된다.

 

풀이 - 1

import java.util.HashSet;
class Solution {
    public int solution(int X, int[] A) {
        HashSet<Integer> countSet = new HashSet<Integer>();
        for(int i=1; i<=X; i++) {
            countSet.add(i);
        }
        
        for(int i=0; i<A.length; i++) {
            if(countSet.contains(A[i])) countSet.remove(A[i]);
            if(countSet.size() == 0) return i;
        }
        
        return -1;
    }
}

 

'풀이 -1'에 대한 회고

 

첫 번째 풀이는 HashSet을 이용해봤다.

어차피 X+1까지 이동하려면 1 ~ X 위치에 나뭇잎이 떨어져야한다.

그래서 1 ~ X까지 먼저 HashSet에 저장하고 배열 A를 반복하며 HashSet에 나뭇잎의 위치 값이 있는지 확인한다.

 

만약 HashSet에 나뭇잎의 위치가 있으면 HashSet에서 요소를 제거해준다.

그리고 HashSet의 크기가 0인지 다시 확인해서 크기가 0이면 현재 index를 반환해준다.

그럼 최소 몇 초가 지나야 X+1까지 개구리가 점프를 할 수 있는지 계산할 수 있다.

아! 배열이 모두 반복 되었는데도 HashSet에 값이 있으면 당연히 개구리는 건널 수 없으니 -1을 반환해주면 된다.

 

그 결과 Score와 정확도, 퍼포먼스가 모두 100% 나왔다.

물론 Time spent는 53min이 나왔지만 이건 제출하는 시기에 따라 조금씩 달라질 수 있으니 무시하련다.

 

 

그리고 중요한 시간 복잡도!

시간 복잡도 또한 O(n)이 나왔다.

 

 

이번 과제는 문제 해석이 조금 오래 걸렸지만 금방 방법을 찾았다.

하지만 뛰는놈 위에 나는놈 있다고~ 다른 개발자들이 어떻게 효율적으로 작성했는지 확인해야겠다.

 

다른 사람의 풀이

import java.util.HashSet;
class Solution {
    public int solution(int X, int[] A) {
        HashSet<Integer> countSet = new HashSet<Integer>();
       
        for(int i=0; i<A.length; i++) {
            countSet.add(A[i]);
            if(countSet.size() == X) return i;
        }
        
        return -1;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

나는 바보야?

굳이 HashSet에 1부터 X까지 미리 담을 필요가 없다.

어차피 배열 A에는 1~X까지의 값밖에 들어가지 못한다.

그러니까 HashSet에 값을 담아가면서 크기가 X랑 같으면 반환하면 된다.

 

아! 참고로 나와 비슷하게 문제를 해결한 사람들도 있다.

물론 HashSet 말고도 List를 사용하는 사람도 있었다.

HashSet에는 어차피 중복 값이 들어갈 수 없으니 시도해본 것인데

조금 더 생각해서 불필요한 프로세스를 찾아 제거하는 연습을 해야겠다.

 

참고로 정확도, 퍼포먼스, 시간 복잡도가 '풀이 - 1'과 동일하게 나왔다.