해당 값의 인덱스 위치를 출력하는 find() 함수를 썼을 때 시간초과가 났다.
find() 함수는 순차탐색 하니까 시간복잡도가 O(N) 이다.
이미 정렬된 곳에서 탐색하는 거니까 이진 탐색으로 구현된 lower_bound() 를 쓰니까 시간초과가 나지 않았다.
시간복잡도를 비교해보자.
find() O(N)
sort O(N logN)
이진 탐색으로 구현된 lower_bound(), upper_bound()
lower_bound() O(log N)
처음 n값이 나오는 위치 반환
upper_bound() O(log N)
처음으로 n값을 초과하는 위치 반환
“맞았습니다" 코드 링크
#include <bits/stdc++.h>
using namespace std;
int n, num;
vector<int> v;
vector<int> temp;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i <n; i++) {
cin >> num;
v.push_back(num); temp.push_back(num);
}
sort(v.begin(), v.end()); // [-10, -9, 2, 4, 4]
v.erase(unique(v.begin(), v.end()), v.end()); // [-10, -9, 2, 4]
for(auto x : temp){
cout << lower_bound(v.begin(), v.end(), x) - v.begin() << ' ';
}
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 막대기 백준 1094번 c++ (0) | 2022.02.17 |
|---|---|
| 수들의 합 백준 1789번 c++ (0) | 2022.02.16 |
| 수 정렬하기 2 백준 2751번 c++ (0) | 2022.02.16 |
| 마인크래프트 백준 18111번 c++ (0) | 2022.02.14 |
| 방 번호 백준 1475번 c++ (0) | 2022.02.14 |