가장 작은 양의 정수 구하기

1. 문제

정수로 이루어진 배열이 있다.

A = [1,3,4,1,2,6] 는 5를 반환하고,

A = [-1,-3]은 1을 반환하고,

A = [1,2,3]은 4를 반환한다.

0보다 크면서, A 배열에 포함되지 않는 가장 작은 양의 정수를 구한다.

 

2. 조건 

1. 배열에 포함된 수는 100,000보다 작은 수 여야한다.

 

3. 풀이

public class Test {
   public int solution(int[] A) {
        int[] B = new int[100];
        int result = 1;
        for(int i=0;i<A.length;i++) {
           if(A[i]>0) B[A[i]]++;
        }
        Boolean flag = false;
        for(int j=1;j<=A.length+1;j++) {
            if( B[j]==0 && (B[j-1]!=0 || B[j+1]!=0) ) {
                result = j;
                break;
            }else {
                flag = true;
            }
        }
        if(!flag) result = 1;
        return result;
   }
}

4. 전략

1. B 배열을 생성하여 A의 값을 인덱스로 하여 1 씩 더해준다. ( 가장 작은 양의 정수를 구하기 위함 )

2. A 배열의 값이 음수일 수 있으므로, A[i] > 0 조건을 부여한다. (B[-1], B[-2] 에 1씩 더해질 수 없기 때문) -- 코드라인 7

3. B 배열에 대해 B[j]가 0이면서 B[j+1]이 0이 아니거나 / B[j-1]이 0이 아닌 경우, j값이 반환 값이므로, for문을 탈출한다. (break) -- 코드라인 11~13

4. A = {-1, -3}의 경우 B = {0,0,0, ... } 이므로 / flag를 false로 초기화하여 1을 반환하게 한다 -- 코드라인 14~18