[codility] FrogRiverOne

(문제) 주어진 배열 A에서 각 시간에 떨어지는 잎들의 위치를 통해 개구리가 반대쪽 강둑으로 건널 수 있는 가장 빠른 시간을 찾는 문제

=> Non Empty Array A와 X값이 주어질 때, 1~X 값이 최소 한 번 이상씩 발견 된 A의 최소 인덱스 값 찾기

(ex) X = 5, A = (1, 3, 1, 4, 2, 3, 5, 4) 일 때 1~5 값이 최소 한 번 이상 발견되는 인덱스는 6이다. (5가 6번 인덱스에 있기 때문에)

 

 

(my solution)

- 영어 독해 해석이 느려서.. 문제 이해하는데 오래걸렸다. (이게 코딩공부인 지 영어 공부인지;;)

- 존재 유무를 O(1)으로 체크해야 하는 문제는 거의 다 HashSet으로만 푸는 것 같다.

- 시간 복잡도는 O(N) => 최악의 경우인 경우

import java.util.HashSet;

class Solution {
    public int solution(int X, int[] A) {
        HashSet<Integer> founded = new HashSet<>();

        for (int i = 0; i < A.length; ++i) {
            int leafPos = A[i];

            if (leafPos > 0 && leafPos <= X) {
                founded.add(leafPos);
            }

            if (founded.size() == X) {
                return i;
            }
        }

        return -1;
    }
}

 

(chatGPT)

- 내가 푼 방법과 동일함 targetLeaves에서 깎으면서 비교하냐 증가시켜서 length와 비교하냐의 차이!

import java.util.HashSet;

class Solution {
    public int solution(int X, int[] A) {
        int targetLeaves = X;
        HashSet<Integer> positions = new HashSet<>();

        for (int i = 0; i < A.length; i++) {
            if (A[i] <= X && !positions.contains(A[i])) {
                positions.add(A[i]);
                targetLeaves--;

                if (targetLeaves == 0) {
                    return i;
                }
            }
        }

        return -1;
    }
}