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

1. 이전 코드 분석

#include <algorithm>

int solution(int X, vector<int> &A) {

    int max_pos = 0;
    for(int leaf = 1; leaf <= X; leaf++)
    {
        auto pos = find(A.begin(), A.end(), leaf); //속도 O(N)
        if(pos == A.end()) return -1; 
        int idx = distance(A.begin(), pos); 
        if(idx > max_pos) max_pos = idx; 
    }

    return max_pos;
}

std::find 함수를 통해서 vector A에서 값을 찾고 있다. 

std::find 함수의 실행 속도는 O(N)이다.

코드에서 반복문이 하나지만, 사실상 이중반복문을 쓰고 있는 것이다.

 

 

2. 속도 개선 아이디어

vector A에서 1부터 X까지 값을 매번 찾지 않고, 연관 배열(map)을 이용한다.

map에서 insert 함수와 find 함수의 실행 속도는 \( O(log{N}) \) 이다.

 

 

2. 코드 (C++)

#include <map>

int solution(int X, vector<int> &A) {

    map<int, int> leaves = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = leaves.find(A[i]);
        if(it != leaves.end()) continue; //이미 넣었던 값
        leaves.insert(pair<int, int>(A[i], 1)); //새로운 값
        if(leaves.size() == (size_t)X) return i; //최소 값 찾았다, 종료
    }

    return -1;
}

 

 

3. 결과