Codility 4.1 FrogRiverOne

문제

• FrogRiverOne
• 배열 A와 정수 X가 주어진다.
• 배열 A에는 각 초(index)마다 떨어지는 나뭇잎의 위치가 저장되어 있다.
  • ex) A가 [3,1,2,5,4]일 경우, 0초에는 3의 위치에 나뭇잎이, 1초에는 1의 위치에 나뭇잎이 떨어진다 ...
• 개구리가 1에서 X 까지 이동하는 데에 걸리는 최소 시간을 구하는 문제이다.
• 즉, 배열을 순회하며 1~X까지의 모든 수가 나타나는 최소 index를 구하면 된다.

풀이

import java.util.HashSet;


class Solution {
    public int solution(int X, int[] A) {
        HashSet set = new HashSet();

        for (int ii = 0; ii < A.length; ii ++) {
            if (!set.contains(A[ii]) && A[ii] <= X) {
                set.add(A[ii]);
            }
            if (set.size() == X) return ii;
        }

        return -1;
    }
}

• HashSet을 사용하여 해결했다.
• HashSet의 부모 클래스인 Set은 중복저장을 허용하지 않으며, add, contains에 O(1)이 걸리기 때문에 문제에 매우 적합한 자료 구조였다.
• 따라서 1~X 사이의 수이며 아직 set에 없는 수를 계속 add하고, set의 크기가 X와 같아지면(1~X 구간의 모든 수가 set에 저장되면) index를 반환하게 하였다.
• 만약 배열을 모두 순회해도 1~X의 모든 수가 set에 저장되지 않았을 경우, -1을 반환하게 하였다.