백준 C++ 18870번 좌표 압축

백준 C++ 18870번 좌표 압축

- 문제 정의

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

솔직하게 여기까지만 보고 개인적으로 이해는 못했습니다
밑에 출력 예시와 다른 사람들이 남긴 질문들을 보고 이해를 할 수 있었습니다.

 

예제 입력 1 복사

5
2 4 -10 4 -9

예제 출력 1 복사

2 3 0 3 1

 

여기서 입력을 보면 첫줄에는 입력 받을 숫자갯수 두번째 줄에는 입력한 숫자들이 있습니다.

위 예시에서 입력한 숫자들을 오름차순으로 나열하면
"-10, -9, 2, 4, 4"가 됩니다.

여기서 중복된 숫자를 제거하면

"-10, -9, 2, 4"가 됩니다.

-10은 배열의 0번째

-9는 배열의 1번째

2는 배열의 2번째

4는 배열의 3번째가 됩니다.

 

출력 값인 "2, 3, 0, 3, 1"과 비교해보면 입력된 숫자들을 오름 차순으로 배열한 뒤 중복된 숫자를 제거한 배열의 인덱스 값이 처음 입력한 순서대로 출력되는 것 이라고 볼 수 있습니다.

 

그럼 이 문제를 풀때는 위에서 제가 한것 처럼

1. 오름차순으로 정렬하고

2. 중복된 숫자를 제거하고

3. 각 숫자의 인덱스를 처음 입력받은 순서대로 내보내면 됩니다.

 

그럼 코드의 첫줄부터 설명하겠습니다.

 

0.준비

ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

: 맨 처음 세줄은 속도 제한이 있기 때문에 최대한 빨리하기 위해 stdio와의 연결을 끊은 것 입니다. 이렇게 하면 c언어의 입출력을 비활성화하여 동기화를 하지 않아 조금 더 빨라집니다.

 

int N; //숫자개수
    cin >> N;
    
    vector<int> number(N);
    
    for(int i = 0; i < N; i++){
        cin>>number[i];
    }
    vector<int> _number(number);

: N을 입력받고 N크기의 number int형 벡터를 선언하였고

number에 입력값을 넣어준 뒤 _numberd에 number값을 복사하여 저장하였습니다.

 

벡터로 선언한 이유는 벡터에 있는 유용한 함수들을 사용하기 위해서 입니다.

 

1.오름차순으로 정렬

sort(_number.begin(), _number.end());

: sort는 유명 정렬 함수입니다. sort(배열 시작, 배열 끝)을 넣어주면 오름차순으로 정렬해 줍니다.

벡터변수명.begin/end()를 하면 벡터의 시작/ 끝 값을 가져올 수 있기에 저는 이것을 사용하였습니다.

 

2.중복된 숫자 제거

 

_number.erase(unique(_number.begin(), _number.end()), _number.end());

: unique함수는 중복 값을 뒤로 보내는 함수 입니다. 그리고 뒤로 보낸 중복 값의 시작 인덱스를 반환하기에 그걸 응용하여 벡터의 요소를 지우는 함수인 erase에 넣으면 중복된 값을 지울 수 있습니다.

벡터명.erase(시작 값 = unique(시작값, 종료값), 종료값) 이 되겠네요

 - 저는 출력할때 배열의 값을 넘기면 지웠던 중복 값이 돌아오는 버그가 있었습니다...

 

3. 입력받은 순서대로 정렬된 숫자들 인덱스 출력

for(int i = 0; i < N; i++){
        auto it = lower_bound(_number.begin(), _number.end(), number[i]);
        cout << it - _number.begin()<<" ";
    }

 :처음에 저는 복사하였던 _number를 정렬하여 number[i]의 값이 변동되지 않게 하였습니다.

이제 정렬된 _number와 number[i]를 이용하여 입력받은 순서대로 정렬된 숫자들의 인덱스를 출력하겠습니다.

우선 위치를 받기 위해 lower_bound라는 함수를 사용하였습니다. 쉽게 설명하자면 number[i]이상의 숫자가 처음 등장한 위치를 반환합니다. 이 위치를 it에 넣어 주었습니다.

(it의 변수명은 auto로 알아서 변수가 어떤 형인지 인식하게 해주는 것 입니다)

이후 _number의 시작부분 위치를 it에서 빼주면 찾는 수의 인덱스가 나오게 되며 이것을 출력해주면 됩니다.

위 코드에서는 입력받은 순서대로 찾고 바로 출력하였습니다.

 

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; //숫자개수
    cin >> N;
    
    vector<int> number(N);
    
    for(int i = 0; i < N; i++){
        cin>>number[i];
    }
    vector<int> _number(number);
    sort(_number.begin(), _number.end());
    
    _number.erase(unique(_number.begin(), _number.end()), _number.end());
    
    for(int i = 0; i < N; i++){
        auto it = lower_bound(_number.begin(), _number.end(), number[i]);
        cout << it - _number.begin()<<" ";
    }

    return 0;
}