백준, BOJ, 18870번 C++ [CPP]

어렵지 않았지만

방법이 조금 틀렸다.

 

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

---

find에 대한 오해가 생겨서 시간 초과가 났다.

 

# 시간 초과 풀이

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;



int N;
vector<int> vec;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    //중복을 허용하지 않고 해당 값보다 작은 값을 선택해야한다. set을 이용하기로함
    while(N--){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    
    //set은 중복을 제거하면서 sort도 함
    set<int> s(vec.begin(), vec.end());
    vector<int> v(s.begin(), s.end());
    
    for(int n : vec){
        auto it = find(v.begin(), v.end(), n);
        cout << it - v.begin() << " "; 
    }
}

 

find가 정렬되어 있어서 N개의 원소를 가지더라도 맨 왼쪽에서 발견되면... 발견하자마자 return할 줄 알았는데..?

아닌가보더라.

 

 

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 경계값 iterator 찾기 lower_bound() 와 upper_bound()

 

 

그래서 lower_bound()를 썼다.

binary search라서 더 빠르게 탐색한다고 한다.

# 맞는 풀이

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int N;
vector<int> vec;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    //중복을 허용하지 않고 해당 값보다 작은 값을 선택해야한다. set을 이용하기로함
    while(N--){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    
    //set은 중복을 제거하면서 sort도 함
    set<int> s(vec.begin(), vec.end());
    vector<int> v(s.begin(), s.end());
    
    for(int n : vec){
        //find함수로 찾으면.. 시간 초과가 난다고 한다.(복잡도가 O(N)이기 때문에..ㅎ)
        auto it = lower_bound(v.begin(), v.end(), n);
        cout << it - v.begin() << " "; 
    }
}

 

find는 선형적인 탐색

lower_bound는 이진탐색

기억해봄직 하다.