배열의 인덱스를 조정해서 푼 문제풀이

MissingInteger

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        Set<Integer> mark = new HashSet<>();
        int N=1;
        
        for(int i=0; i<A.length; i++){
            mark.add(A[i]);
        }
        
        List<Integer> list = new ArrayList(mark);
        
        Collections.sort(list);
        
        if(A.length == list.size() ){
            N = list.get(list.size()-1)+1;
        }else{
            for(int j=0; j<list.size(); j++){
            if(list.get(j) != j+1 && list.get(j)>0){
                N = j+1;
                break;
                }
            }

            
        }
        return N;
        
                
    }

주어진 A배열의 원소들을 HashSet mark에 담아 중복을 제거한뒤,
정렬된 list 객체에 담는다.

정렬된 list객체의 size와 A의 length를 비교하여

빠진 원소가 있는지 판별하고 빠진원소가 있을 경우에는
배열내 가장 큰원소에 1을 더해 리턴값을 산출.

빠진 원소가 없을 경우에는 for문을 통해
최대값을 찾고, 최대값+1을 리턴하는 알고리즘으로 만들었었다.

이번건 좀 어려웠다.

A배열 원소의 범위가 너무 넓어서

생각해서 풀기에는 예외적인 상황들이 일어날 가능성이 너무 많았고,
퍼포먼스를 고려하지않고 정확성 100프로를 달성하는것도 좀어려웠다.

문제를 풀고 하루가 지나서 다른분들이 푼 결과를 참고해보니
boolean 배열을 통해 문제를 해결했더라

import java.util.*;

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        boolean checker[] = new boolean[A.length+1];
        
        for(int i=0; i<A.length; i++){
            int value=A[i];
            if(value>0 && value<checker.length){
                checker[value]=true;
            }
        }
        
        for(int i=1; i<checker.length; i++){
            if(checker[i]==false){
                return i;
            }
        }
        return checker.length;
    }
}

boolean 값으로 이루어진 배열을 선언하고

for문을 만들었는데 A배열의 원소를 for문의 인덱스로 사용해
checker배열의 원소의 값을 true 로 바꿔준다.

첫번째 for문을 통해 연속되는 A배열 원소들의 연속성을 판단할 수 있도록 checker배열을 채우는것이다.
(문장이 좀 어색하네요 :()

마지막으로 나오는 for문에서는 checker배열을 순서대로 판별해 true값이 아닌 인덱스를 반환하는 알고리즘이다.

세번째 예시 int A[] = { -1, -3 } 이 경우에는 첫번째 for문에서 true가 되는 과정이 없다. 그래서 boolean 배열의 상태를 나타내보면

value false false false
index 0 1 2

이렇게 boolean 배열의 초기값 false로만 이루어진 상태이기때문에
두번째 for문의 초기값 int i = 1 에서 1 이 리턴되는 알고리즘이다.