[codility] MissingInteger

(문제) A 배열이 주어질 때, 빠진 자연수 찾기

 

1차 시도 결과(버블 정렬 사용)

2차 시도 결과

 

(my solution)

- 처음에는 Bubble Sorting을 통한 정렬 후 missingInteger를 찾는 방향으로 짰다.

- 왜냐하면 int A = {3, 4, 5} 일 때 6이 반환된다고 생각했기 때문 (하지만 이런 형태로 A가 주어지는 경우는 없다.)

- 그냥 단순하게 배열을 순회하면서 HashSet에 값을 넣고, 1부터 증가시켜 가면서 빠진 값을 리턴해주면 끝난다.

- 결론: 불필요한 케이스를 생각했고 단순한 문제를 복잡하게 풀었다.

- 시간 복잡도는 O(N^2) --> O(N)으로 감소했다.

- 이참에 정렬 복습이나 해야겠다.

package codility.tasks;

import java.util.HashSet;

public class MissingInteger {
    public static int solution(int[] A) {
        HashSet<Integer> founded = new HashSet<>(A.length);

        for (int num : A) {
            founded.add(num);
        }

        int i;
        for (i = 1; i < A.length + 1; ++i) {
            if (!founded.contains(i)) {
                return i;
            }
        }

        return i;
    }
}

 

 

(chat GPT)

- 내가 푼 방식과 동일하다.

- 디테일이지만 두 번째 반복문에서 i의 반복조건을 i <= A.length + 1 로 두는 게 더 좋은 것 같다.

- 왜냐하면

1. return 값이 i와 -1로 나눠져서 다른 케이스라는 게 이해가 더 잘 됨

2. int i를 for문에서 선언할 수 있어서 불필요한 라인이 줄어듬

import java.util.HashSet;

class Solution {
    public int solution(int[] A) {
        HashSet<Integer> seen = new HashSet<>();
        
        for (int num : A) {
            if (num > 0) {
                seen.add(num);
            }
        }
        
        for (int i = 1; i <= A.length + 1; i++) {
            if (!seen.contains(i)) {
                return i;
            }
        }
        
        return -1;
    }
}