백준 18870번 [좌표 압축](C++)-yes6686- 티스토리

백준 문제 풀이: 18870 [좌표 압축]

---

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

문제 설명:

주어진 N개의 정수 배열에서 각 정수의 크기를 상대적인 순위로 압축하여 출력하는 프로그램을 작성하세요. 좌표 압축은 다음 규칙에 따라 진행됩니다:

• 중복된 값은 하나의 순위로 표현합니다.
• 작은 값부터 0, 1, 2...와 같은 방식으로 순위를 부여합니다.

입력 조건:

• 첫째 줄에 N (1 ≤ N ≤ 1,000,000)이 주어집니다.
• 둘째 줄에는 배열의 원소로 -10⁹ 이상 10⁹ 이하의 정수 N개가 주어집니다.

출력 조건:

• 각 원소의 좌표 압축 결과를 공백으로 구분하여 출력합니다.

---

문제 해결 코드

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

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

    int n;
    cin >> n;

    vector<int> arr(n);      // 입력 배열
    vector<int> sorted_arr; // 정렬된 배열
    unordered_map<int, int> rank_map; // 좌표 압축을 위한 해시 맵

    // 배열 입력 받기
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sorted_arr.push_back(arr[i]);
    }

    // 배열 정렬 및 중복 제거
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());

    // 압축 순위 부여
    for (int i = 0; i < sorted_arr.size(); i++) {
        rank_map[sorted_arr[i]] = i;
    }

    // 좌표 압축 결과 출력
    for (int i = 0; i < n; i++) {
        cout << rank_map[arr[i]] << ' ';
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 배열에서 각 원소의 상대적인 순위를 구해 좌표 압축 결과를 출력합니다.

• 입력 및 정렬:
  • `arr` 배열에 입력받고, `sorted_arr`에 복사하여 정렬합니다.
  • 중복 값을 제거하기 위해 `unique`를 사용합니다.
• 순위 매핑:
  • 정렬된 배열의 각 값에 대해 0부터 순차적으로 순위를 부여합니다.
  • 이를 해시 맵에 저장하여 검색을 빠르게 합니다.
• 출력:
  • 원래 배열 `arr`의 각 값에 대해 해시 맵에서 순위를 찾아 출력합니다.

시간 복잡도 분석:

• 정렬: O(N log N).
• 중복 제거: O(N).
• 맵에 순위 저장 및 조회: O(N).

따라서 전체 시간 복잡도는 O(N log N)입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5
2 4 -10 4 -9

출력:
2 3 0 3 1

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!