codility Lesson4 - PermCheck

코드

시간복잡도: 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;
#include <set>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    int len = 0;
    set<int> s;
    for(auto a: A) {
        if(a > A.size()) return 0;
        s.insert(a);
        if(s.size() == len) return 0;
        else {
            len = s.size();
        }
    }

    return 1;
}

풀이 및 소감

bool 배열을 사용할까 하다가 전 문제에서 set을 안 썼던 게 기억나서 set을 사용해줬다. size()를 사용 안 하고 set에 이미 있는 지 확인해도 되겠지만 검색을 안 하면서 풀어보려고 길이의 변화로 문제를 해결했다. 다른 사람들 풀이를 보니 정렬을 사용했는데 정렬을 사용해서 풀 수 있다는 걸 자주 까먹는 거 같다 ㅠㅠ