4-1. FrogRiverOne
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개의 정수로 구성된 배열 A를 받습니다. A[K]는 시간 K(초 단위)에 한 나뭇잎이 떨어지는 위치를 나타냅니다.
목표는 개구리가 강의 반대편으로 점프할 수 있는 가장 빠른 시간을 찾는 것입니다. 개구리는 강의 모든 위치(1에서 X까지)에 나뭇잎이 나타날 때만 건널 수 있습니다(즉, 1에서 X까지의 모든 위치가 나뭇잎으로 덮이는 가장 빠른 순간을 찾고자 합니다). 강의 흐름 속도는 무시할 수 있을 정도로 작다고 가정할 수 있습니다. 즉, 나뭇잎이 강에 떨어지면 위치가 변하지 않습니다.
예를 들어, 정수 X = 5와 배열 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 6초에 나뭇잎이 위치 5에 떨어집니다. 이것은 나뭇잎이 강의 모든 위치에 나타나는 가장 빠른 시간입니다.
비어 있지 않은 배열 A와 정수 X가 주어졌을 때, 개구리가 강의 반대편으로 점프할 수 있는 가장 빠른 시간을 반환합니다.
개구리가 강의 반대편으로 점프할 수 없는 경우, 함수는 -1을 반환해야 합니다.
문제풀이
import java.util.*;
class Solution {
public int solution(int X, int[] A) {
HashSet<Integer> leafs = new HashSet<Integer>();
for(int i = 0; i < A.length; i++){
if(A[i] <= X){
leafs.add(A[i]);
}
if(leafs.size() == X){
return i;
}
}
return -1;
}
}
HashSet(중복되지 않는 데이터를 순서에 상관없이 저장)을 사용해서 A배열의 값들이 X(강의 위치)보다 작거나 같을 경우에만 hashset에 추가하고 hashset의 크기가 X와 같아진다면 return 함수를 통해 "i값" -> A배열의 index 즉 시간을 반환해줍니다.
점프를 할 수 없는 경우는 "-1"을 반환하라고 하였기에 마지막에 return -1;을 추가해줍니다.
실행 결과
문제풀어보기 -> https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/
