[codility] PermMissingElem

(문제) 크기가 N이며 [1..N+1] 사이의 서로 다른 원소를 가지는 배열 A에서 빠진 원소를 찾는 함수 작성

 

(my solution)

- 문제를 잘못 해석했다. 예를 들어 N = 4이고 A = {1, 2, 3, 4} 값을 가지면 1부터 순차적인 값을 가졌으므로 빠진 값이 없다고 잘못 생각했다. (문제 마음대로 해석하지 말고 제대로 읽어라... 부들부들)

- 중복 값이 없고 배열에 어떤 값이 있는 지 O(1)으로 바로 찾고 싶을 때마다 HashSet으로 푸는 것 같다.

- 잘못된 해결법은 아니지만 1) 별도의 메모리 공간이 필요  2) 배열의 크기만큼 순회하면서 HashSet에 값을 넣어야 함. 두 가지 이유로 더 좋은 해결법이 있다면 그 방법으로 푸는 게 좋을 것 같다.

- sum을 이용하면 더 심플하게 풀었다. (문제만 제대로 이해했으면 1분도 안 되서 풀 문제를.... 부들부들)

package codility.tasks;

import java.util.HashSet;

public class PermMissingElem {
    public static int solution(int[] A) {
        if (A.length == 0) {
            return 1;
        }

        HashSet<Integer> hashA = new HashSet<>();
        for (int value : A) {
            hashA.add(value);
        }

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

        return -1;
    }
}

 

 

(chatGPT)

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int totalSum = (N + 1) * (N + 2) / 2; // Sum of integers from 1 to N+1
        int arraySum = 0; // Sum of elements in array A

        for (int num : A) {
            arraySum += num;
        }

        int missingElement = totalSum - arraySum;
        return missingElement;
    }
}