문제풀이(Problem Solving)

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

게임이 더 좋아 2021. 6. 7. 20:01
반응형
728x170

어렵지 않았지만

방법이 조금 틀렸다.

 

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

 

18870번: 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌

www.acmicpc.net

 


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는 이진탐색

기억해봄직 하다.

 

728x90
반응형
그리드형

'문제풀이(Problem Solving)' 카테고리의 다른 글

백준, BOJ, 11562번 C++ [CPP]  (0) 2021.06.08
백준, BOJ, 1181번 C++ [CPP]  (0) 2021.06.07
백준, BOJ, 15650번 C++ [CPP]  (0) 2021.06.06
백준, BOJ, 14501번 C++ [CPP]  (0) 2021.06.06
백준, BOJ, 10814번 C++ [CPP]  (0) 2021.06.06