풀이

• 개구리 어쩌고 되어있지만 결국 문제의 핵심은 두가지인데
  • 중복이 있는 숫자 배열이 주어지고
  • 원하는 원소를 다 모아놨는지 검사하는데
  • 시간복잡도를 n^2 이하로 줄일수 있냐? 의 문제인데요
• 여기서 포인트는 원하는 원소들을 다 모아놨는지 (그러니까 X=5 라면 1,2,3,4,5 모든 원소를 한번이상 빠짐없이 다 모아왔는지(스트레이트 플러쉬) 체크를 빠르게 해야하는게 관건인 그런 코드였습니다.
  • 중복있는 모든 원소를 한번이상 빠짐없이 다 모아왔는지 체크하기 위해서, 자연스럽게 중복이 제거되는 HASH에 원소를 추가했고, size() 메서드를 활용해 N만큼의 시간복잡도를 확보했고,
  • BruteForce 방식의 N^2 시간보다 최적화를 했습니다.

import java.util.HashSet;

class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8

        HashSet<Integer> check = new HashSet<>();
        final int n = A.length;

        for(int i=0 ; i<n ; i++) {
            if(A[i] <= X) {
                check.add(A[i]);
            }

            if(check.size() >= X) {
                return i;
            }
        }
        return -1;

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println( s.solution(5,new int[] {1,3,1,4,2,3,5,4}));
        //6나와라
    }
}