백준 18870 좌표압축 c++ [컴공과고씨]

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

18870번: 좌표 압축

문제 이해

이 문제는 숫자가 나열되어있을 때 자신보다 작은 숫자의 개수로 그 숫자를 바꾸어 주는 것이다.

예를 들면 1 -9 -7 4 4  8 -10 -10 -10 2 3 3 1 이렇게 숫자가 있을 때 정렬을 해주면

-10 -10 -10 -9 -7 1 1 2 3 3 4 4 8 이므로 -7보다 작은 수는 3개이므로 -7 -> 3으로 변하는 것이다.

 

문제 접근 방식

나는 처음에 벡터와 해시맵을 가지고 풀었다. 입력값을 벡터에 받아 정렬을 한 후 해시 맵에 작은 수부터 이 숫자는 몇번째 수인지 기록했다. 그 후 원본 벡터를 가면서 해시맵에서 그 숫자를 찾아 변환 숫자를 찾아주는 식으로 구현했다. 그런데 이 방식은 시간이 오래걸려 성공할 때도 있지만 시간초과에 걸릴 때도 있어 원하는 풀이방식이 아닌걸 알아서 다른 방식으로 또 풀어보았다.

2번째 방법은 lower_bound함수를 이용한 풀이이다.

lower_bound(시작값, 종료값, 찾는 값) 함수는 찾는 값보다 같거나 큰 값을 리턴해주는 함수이다. 이때 리턴값이 iterator 이므로 .begin()을 빼주면 인덱스를 구할 수 있다. 이 함수를 이용하면 쉽게 문제를 풀 수 있다.

먼저 정렬을 한 후 중복값을 제거해준다. 만약 -7 -7 -10 -5 4 5 -5 1 6 이런 수가 주어졌다고 하면 정렬 후 중복제거를 해주면 -10 -7 -5 1 4 5 6 이렇게 된다. 그런 후 원본 벡터를 하나씩 읽으면서 그 수를 찾아주면 -7을 찾으면 lower bound - .begin() => 1반환 이런식으로 해서 쭉 출력해주면 답이 된다.

 

* 중복값 제거 함수 erase 와 unique 활용

unique(x,y)함수는 x부터 y까지 중복된 값이 나온 값을 하나 빼고 나머지는 맨뒤로 보내고 그 인덱스를 리턴함.

unique함수는 정렬이 되어있어야 정확하게 중복된 값을 제거 할 수 있음.

erase(x,y) x부터 y까지 있는 수를 제거

 

 

단계별 문제 풀이

1. 벡터 두 개 선언 (정렬 벡터, 원본 벡터)

2. 벡터 정렬 후 중복 값 제거 

3. 원본 벡터의 하나씩 lower_bound함수에 넣어 인덱스 값 출력

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
 
int main(){
    int n;
    long long temp;
    vector<long long> x1;
    vector<long long> x2;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> temp;
        x1.push_back(temp); // 정렬 벡터
        x2.push_back(temp); // 원본 벡터
    } 
    sort(x1.begin(), x1.end()); // 정렬
    x1.erase(unique(x1.begin(), x1.end()), x1.end()); // 중복값 제거
 
    for (int i = 0; i < n; i++){
        cout << lower_bound(x1.begin(), x1.end(), x2[i]) - x1.begin() << " ";  // 몇 번째로 작은 수인지 리턴
    }
} // lower_bound 이용 함수 
 
/*int main(){
    cin.tie(0);
    cout.tie(0);
    int n;
    long long temp;
    vector<long long> x;
    vector<long long> x2;
    map<long long, int> xi;
    
    cin >> n;
    for (int i = 0; i < n;i++){
        cin >> temp;
        x.push_back(temp);
        x2.push_back(temp);
    }
    sort(x.begin(), x.end());
    temp = x[0];
    int cnt = 0;
    xi.insert(make_pair(x[0], cnt));
    for (int i = 0; i < n; i++){
        if(temp != x[i]){
            cnt++;
            xi.insert(make_pair(x[i], cnt));
            temp = x[i];
        }
    }
    for (int i = 0; i < n;i++){
        cout << xi[x2[i]] << " ";
    }
    return 0;
} hash 이용 -> 시간 오래걸림 */

체감 난이도	걸린 시간	참고	사용 알고리즘, 문법	기타
중	해시 (30min) lower_bound 공부후 (15min)	해시가 너무 오래걸려 다른 방법 검색하여  lower_bound함수를 쓰면 쉽게 풀 수 있다는 것을 참고함	lower_bound unique erase	중복 제거 아이디어를 떠올리지 못해서 해시로 접근해서 시간이 오래걸리는 알고리즘을 짬