반응형
728x170
어렵지 않았지만
방법이 조금 틀렸다.
https://www.acmicpc.net/problem/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는 이진탐색
기억해봄직 하다.
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 |