일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 자료구조
- Articulation_Point
- sort
- data_structure
- STL
- Heap
- sstream
- 백준
- template
- 구현
- qsort
- function_template
- c++
- Algorithm
- class_template
- 문법
- list
- 13305
- 예제
- Biconnected_Component
- singly Linked List
- '0'
- Critical_Path_Analysis
- 총정리
- deletion
- 5397
- red-black tree
- 알고리즘
- connected_component
- Pair
- Today
- Total
- Today
- Total
- 방명록
어제의 나보다 성장한 오늘의 나
[c++][문제 풀이] 백준 18870번 <좌표 압축> 본문
문제 설명
입력된 값들 각각 자신 보다 작은 값이 몇 개 있는 지를 입력된 순서대로 출력 하면 되는 문제이다.
단 , 자신 보다 작은 값을 셀 때 중복 된 값들은 1개로 처리 된다.
문제 풀이
시간 제한은 2초.
입력 값은 0 ~ 10^6 까지 이다.
시간복잡도 O(N^2) 로는 풀 수 없고 O(NlogN) 으로 풀어야 한다.
algorithm 의 sort 함수 -> O(NlogN)
algorithm 의 lower_bound ->(O(logN) 함수 * N번) 를 사용할 것이다.
Coding
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int args ,char ** argv){
int N; // 좌표의 갯수
int X; // 좌표 값
vector<int> v; // 중복 제거 , 오름차순 정렬 할 벡터
cin >> N;
while(N--){
cin >> X;
v.push_back(X);
}
vector<int> v_before(v); // 입력 된 그대로의 벡터.
sort(v.begin() , v.end()); // 오름차순 정렬
v.erase(unique(v.begin() , v.end()), v.end()); // 중복 제거
vector<int> result;
for(int i = 0 ; i < v_before.size() ; ++i){
result.push_back(lower_bound(v.begin() , v.end() , v_before[i]) - v.begin());
}
for(auto x : result){
cout << x << ' ';
}
}
unique , lowerbound 함수에 대해 잘 모르겠다면 아래 글들을 참조 하자
2022.02.13 - [c++/문법] - [C++] Unique 함수 정리 및 예제
[C++] Unique 함수 정리 및 예제
◎ 시간 복잡도 : O(N) ◎ 중복된 값을 제거 하기 위해 사용하는 함수 ◎ 의 sort와 erase와 함께 사용함. ◎ 반드시 정렬을 해준 뒤 사용한다. 헤더파일 #include 사용법 vector v = { 2, 3, 5 , 2, 3, 5 ,4}; so..
8156217.tistory.com
2022.02.13 - [c++/문법] - [c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제
[c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제
공통 특징 ◎ 헤더파일 : ◎ iterator 사용 / 반환 ◎ 이진 탐색 구조 / 시간 복잡도 : O(log N) ◎ 오름차순 정렬되어 있어야 한다. ◎ 찾는 값이 벡터/배열 속에 여러 개 있을 경우 가장 앞에 있는 값을
8156217.tistory.com
백준 18870번 문제 링크
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
'c++ > 백준 문제 풀이' 카테고리의 다른 글
[c++][Greedy] 백준 10610번 문제 풀이 (0) | 2022.02.22 |
---|---|
[c++][Greedy] 백준 1789번 문제 풀이 (0) | 2022.02.22 |
[c++][Greedy] 백준 11399번 문제 풀이 (0) | 2022.02.20 |
[c++][Greedy] 백준 1541번 문제 풀이 (0) | 2022.02.19 |
[c++][Greedy] 백준 13305번 문제 풀이 (0) | 2022.02.19 |