https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/
문제
- 작은 개구리가 0위치에서 시작해서 X+1위치까지 건너가고 싶어한다.
- A 배열은 각 위치에 나뭇잎이 떨어지는 시간( second )를 나타낸다.
- 작은 개구리는 건너가고자 하는 모든 위치에 나뭇잎이 존재해야지만 건너갈 수 있다.
- 목표 위치까지 가장 빠르게 건널 수 있는 시간을 구해라.
제한조건
- N and X are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..X].
N과 X는 1 ~ 100,000 사이의 정수이다.
A의 각 원소는 1 ~ X 사이의 정수이다.
풀이
- answer = -1로 초기화 하고, 최소 시간이 나올 경우에는 answer값에 대입한다.
- road라는 임의의 boolean 배열을 선언하여 시간 때마다 떨어진 위치의 나뭇잎을 체크한다.
- road 배열에서 지나가지 않은 위치에 나뭇잎이 떨어질 때, cnt 변수를 +1하고, cnt변수와 (road배열의 크기 - 1)을 비교하여 체크한다.
참고 : 편의를 위해 road 배열은 X+1로 초기화 한다. ( index를 맞추기 위해서 )
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int X, int[] A) {
// write your code in Java SE 8
boolean[] road = new boolean[X + 1];
road[0] = true;
int cnt = 0;
int answer = -1;
for( int i=0; i<A.length; i++ ){
// 1. 위치에 나뭇잎이 존재하지 않는 경우
if( !road[A[i]] ){
road[A[i]] = true;
cnt++;
if( cnt == (road.length - 1) ){
answer = i;
break;
}
}else{
continue;
}
}
return answer;
}
}
'코딜리티 문제풀이' 카테고리의 다른 글
Codility Lesson 04 - MaxCounters( JAVA ) (0) | 2022.03.19 |
---|---|
Codility Lesson 04 - PermCheck( JAVA ) (0) | 2022.03.19 |
Codility Lesson 03 - TapeEquilibrium( JAVA ) (0) | 2022.03.16 |
Codility Lesson 03 - PermMissingElem( JAVA ) (0) | 2022.03.14 |
Codility Lesson 03 - FrogJmp( JAVA ) (0) | 2022.03.13 |