백준 c++ 18870 문제 풀이

문제 링크 : https://www.acmicpc.net/problem/18870

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 2 문제 입니다.

문제명 : 좌표 압축

 

내 코드

#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

    int N;
    cin >> N;

    vector<int> arr(N);

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    vector<int> sortedArr = arr;

    sort(sortedArr.begin(), sortedArr.end());
    sortedArr.erase(unique(sortedArr.begin(), sortedArr.end()), sortedArr.end());

    for (int i = 0; i < N; i++) 
    {
        int idx = lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin();
        cout << idx << " ";
    }

}

 

문제 풀이 해석 내용

 

입출력 최적화

ios::sync_with_stdio(false);
cin.tie(NULL);
std::cout.tie(NULL);

입출력을 더 빠르게 하기 위해 C++의 동기화를 비활성화합니다.

 

 

변수 선언 및 입력 처리

int N;
cin >> N;

vector<int> arr(N);

for (int i = 0; i < N; i++)
{
    cin >> arr[i];
}

N: 배열의 크기를 저장할 변수입니다.
arr: 크기가 N인 정수형 벡터를 생성하고, 사용자로부터 입력받은 값을 저장합니다.

 

 

정렬 및 중복 제거

vector<int> sortedArr = arr;
sort(sortedArr.begin(), sortedArr.end());
sortedArr.erase(unique(sortedArr.begin(), sortedArr.end()), sortedArr.end());

sortedArr를 arr로 초기화합니다.
sort 함수를 사용하여 sortedArr를 오름차순으로 정렬합니다.
unique 함수를 사용하여 중복된 값을 제거합니다. 

이 함수는 중복된 요소를 배열의 끝으로 이동시키고, 새로운 끝 위치를 반환합니다. 

erase를 통해 중복된 부분을 삭제합니다.

 

 

좌표 압축 및 결과 출력

for (int i = 0; i < N; i++) 
{
    int idx = lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin();
    cout << idx << " ";
}

for 루프를 통해 원래 배열 arr의 각 원소에 대해 반복합니다.
lower_bound 함수를 사용하여 sortedArr에서 현재 원소 arr[i]가 들어갈 위치의 iterator를 찾습니다. 

이 iterator에서 sortedArr.begin()을 빼면 해당 원소의 인덱스를 계산할 수 있습니다.
계산된 인덱스를 출력합니다. 이 인덱스는 압축된 좌표를 나타냅니다.

---

iterator : c++에서 사용되는 객체로, 컨테이너의 요소에 접근하기 위해 사용됩니다.

iterator는 포인터와 유사한 역할을 하며, 컨테이너의 요소를 순회하거나 수정하는 데 유용합니다.

 

 

실행 결과