문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
이번 문제는 좌표압축이 뭔지 배우는것부터 시작했다.
좌표압축의 개념은 아래 포스팅에서 정리했고,
좌표 압축 알고리즘 이란?
백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알아야 할 것 같아서 정리해본다. 좌표 압축 알고리즘이란? : 모든 구간이 아니라, 중요한 구간이나, 숫자만 들고있는 기��
runa-nam.tistory.com
이걸 가지고 문제를 바로 풀기에는 개념이 너무 어색해서, 먼저 다른사람들의 풀이를 보고 이를 분석하여 푸는 방식으로 진행하였다.
여기에서 새롭게 배운 개념중 하나는 lower_bound함수였는데, 이 함수는 <algorithm> 헤더 안에 포함되어있으며, 먼저 sort 함수를 통해 정렬되어있어야한다는 전제가 필요하다.
lower_bound(first, end, x) 는 first ~ end에서 x이상의 값이 나오는 첫번째 원소의 위치를,
upper_bound(first, end, x) 는 first ~ end에서 x초과의 값이 나오는 첫번째 원소의 위치를 반환한다.
또한 unique, resize함수를 사용해서 정렬한 배열의 중복을 제거하는 방식또한 배웠다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> v, idx;
int main(void)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int a;
scanf("%d", &a);
v.push_back(a);
idx.push_back(a);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int a : idx)
{
int pos = lower_bound(v.begin(), v.end(), a) - v.begin();
printf("%d ", pos);
}
}
'백준 문제풀이' 카테고리의 다른 글
[백준/C++] 11723 집합 (0) | 2020.08.28 |
---|---|
비트마스크 란? (0) | 2020.08.28 |
좌표 압축 알고리즘 이란? (0) | 2020.08.28 |
[C++/백준] 11724 연결요소의 개수 (0) | 2020.08.22 |
[C++/백준] 11399 ATM (0) | 2020.08.21 |