[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–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

[문제]

개구리가 강의 둑(position 0)에서 반대편 둑(position X+1)으로 갈 수 있는 최소 시간을 찾는 것.

초마다 잎이 어떤 위치에 떨어지고 1~X까지 모든 위치에 잎이 떨어져야 개구리가 강을 건널 수 있다.

즉, 1~X까지 모든 숫자가 들어있는 배열 index의 최솟값을 찾는 것이라고 볼 수 있다. (중복 상관 X)

 

 

[문제풀이]

public static int solution(int X, int[] A) {
	int answer = -1;
	boolean[] check = new boolean[X];
	
	for(int i=0; i<A.length; i++) {
		check[A[i]-1] = true;
		
		for (int j=0; j<check.length; j++) {
			if (!check[j]) {
				break;
			}
			
			if (check[j] && j == check.length-1) {
				answer = i;
				return answer;
			}				
		}
	}
	
	return answer;
}

처음 문제를 풀 때는 position을 체크하는 배열을 만들어 해당 position에 잎이 떨어졌으면 true로 바꿔주고 모든 배열이 true가 되었을 때 return 하는 것으로 작성했다.

예상했던 대로 정확도는 100%가 나왔지만 퍼포먼스 체크에서 시간 복잡도 O(n²)으로 실패하여 전체 스코어가 50%가 나왔다.

 

public static int solution(int X, int[] A) {
	int answer = -1;
	Map<Integer, Integer> check = new HashMap<>();
	
	for (int i=1; i<=X; i++) {
		check.put(i, i);
	}
	
	for (int i=0; i<A.length; i++) {
		if (check.containsKey(A[i])) {
			check.remove(A[i]);
		}
		
		if (check.isEmpty()) {
			answer = i;
			return answer;
		}
	}
	
	return answer;
}

두 번째로 다시 풀 때는 배열을 사용하는 대신 HashMap을 사용했다.

배열을 사용했을 때 배열 index 전체를 순회하며 체크하는 대신 HashMap에 Key가 있는지 체크하고 있으면 제거하는 방법을 사용했다.

만약 HashMap이 비어있다면 position X까지 모든 잎이 떨어져 있는 것이므로 해당 index를 return 한다.

 

 

[결과]

Test Score 100%!!!!

 

시간복잡도 O(N)

 

다른 알고리즘 사이트들 보다도 Codility는 스코어가 나와서 그런가 풀이할 때마다 더 뿌듯한 느낌이다.

하루에 조금씩이라도 꾸준히 알고리즘 풀이를 해나가야지 하고 다짐하는 요즘.

 

---

+ 19.04.21

HashMap이 아닌 HashSet으로 풀이하면 더 편하게 풀이가 가능하다..!