[백준 18870] 좌표 압축

좌표 압축

문제설명

좌표 압축의 개념을 사용하여 주어진 좌표를 압축한 결과를 출력한다.

예제를 보고 좌표 압축의 개념에 대해서 설명하도록 하겠다.

먼저 5개의 수를 입력받고, 좌표 값을 입력 받는다. 첫번째 예제의 경우 크기순으로 나타낸다고 보면 된다. -10이 값이 제일 작기때문에 0번째 인덱스, -9는 1 이런식의 값을 가지게 된다.

다만 유의해야할 점은 중복 된 값이 들어올 수 있다는 점이다.

2번째 예제의 경우 좌표의 값이 중복 되는 케이스이다.
999, 1000이 중복되어 나오는데 이 역시도 포함해서 결과가 나오는 것을 확인할 수 있다.

알고리즘

1. 총 좌표의 수 값을 입력 받는다.
2. list에 좌표 값을 입력 받는다.
3. set(집합)개념을 사용하여 중복좌표 값을 제거하고, 오름차순으로 정렬한다.
4. dictionary개념을 사용하여 key에는 좌표값, value에는 index 값을 저장한다.
5. 원래의 list를 순회하여 key를 통해 value를 출력시킨다.

---

n=input() #숫자 수 입력 받기

arr = list(map(int, input().split())) # 좌표 각각 입력 받기
arr2 = sorted(list(set(arr)))  #중복 제거 및 오름차순 정렬

dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
    print(dic[i], end = ' ')

+++++++++++

 

C++ 코드

 

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

int main() {
	vector <int> v,idx;
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
		idx.push_back(x);
	}
	sort(idx.begin(), idx.end());//오름차순 정렬
	idx.erase(unique(idx.begin(), idx.end()), idx.end()); //중복 원소 지우기 

	for (auto a : v) {
		cout << lower_bound(idx.begin(), idx.end(), a) - idx.begin()<<' '; //실제 값이 있는 인덱스 반환
	}
}

고찰

이번 문제는 언어를 파이썬으로 변경하면서 처음 풀어본 문제이다.
파이썬 자료구조형을 잘 몰라서 찾아 보고 풀었다.

정리

1. set(집합): 집합에 관련된 것을 쉽게 처리하게 만든 자료형
   • 중복을 허용하지 않음
   • 순서가 없음
2. dictionary(딕셔너리): key, value 쌍으로 구성되어 있음
   • key 값은 고유한 값으로 설정해야함 그렇지 않은 경우 무시됨

3. map(맵): 함수와 반복가능한 자료형을 입력받고, 입력받은 자료형의 각 요소를 함수가 수행한결과를 묶어서 돌려주는 함수