문제풀이

• 연속한 숫자의 나열인데, 순서가 뒤죽박죽인 체 배열속에 들어있다
• 중간에 연속되지 않고 하나 빠진 정수가 있는데, 그 빠진 정수가 뭔지 알아내는 문제
• 예를들어
  2,4,3,1,7,6 이 들어있으면 정답은 5
• 풀이 핵심 아이디어는 dat 기법을 사용해서 풀었는데
  • 주어진 배열만큼 배열공간을 생성하면 기본 다 0값으로 초기화 되어있으므로
  • 입력배열의 원소 하나하나를 인덱스로 해서 dat를 +1 씩 해주면
  • 자연스럽게 빠져있는 정수값의 인덱스만 0으로 남아있으므로 정답을 구할 수 있다.

class Solution {
    public int solution(int[] A) {
        int[] dat = new int[A.length+2];

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

        for(int i=1 ; i<size+2 ; i++) {
            if(dat[i] == 0) {
                return i;
            }
        }

        return -1;
    }
}