Lesson 4. Counting Elements - FrogRiverOne #3 (속도 개선-2)

1. 속도 개선 아이디어

이 문제를 조금 다르게 해석하면, 다른 해법이 보인다.

문제에서는 '찾는다'라고 표현했지만, 다르게 생각하면 1부터 X까지의 합을 구하는 것과 같다.

즉, vector A의 요소들을 더했을 때, (1 + .. + X)가 되는 시점을 구하면 된다.

 

 

2. 코드 (C++)

int solution(int X, vector<int> &A) {
   
    vector<bool> found_leaves(X, false); //이미 계산한 값인지 확인하기 위한 vector
    int sum = X * (X + 1) / 2; //1부터 X까지의 합

    for(size_t i = 0; i < A.size(); i++)
    {
        int leaf = A[i];
        if(found_leaves[leaf] ==  true) continue; //이미 계산한 값이라면 skip
        found_leaves[leaf] = true; //계산하지 않은 값이라면, 계산한 값으로 표시
        sum -= leaf;
        if(sum == 0) return i;
    }

    return -1;
}

 

 

3. 결과