codility Lesson3 - PermMissingElem

코드

시간복잡도: O(N) or O(N * log(N))

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    long long sum = (A.size() + 1) * (2+A.size()) / 2;
    long long sumA = 0;
    for(auto a : A) {
        sumA += a;
    }

    return sum - sumA;
}

풀이 및 소감

모든 수가 다 있는 경우의 합을 구하 값에서 배열의 합을 구한 값을 빼서 해결했다. 다른 사람들의 풀이를 살펴보니 정렬을 활용한 풀이도 있었다.