[백준/C#] 11870 - 좌표 압축

1. 문제

수직선 위에 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 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

- 설명

예제 입력	예제 출력
5 2 4 -10 4 -9	2 3 0 3 1
6 1000 999 1000 999 1000 999	1 0 1 0 1 0

18870번: 좌표 압축

 

---

2. 풀이

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 하므로, 좌표를 압축하면 가장 작은 수가 0이 된다.

ex) 12, 30, 100, 324, 2100 -> 0, 1, 2, 3, 4

 

입력받은 좌표 배열의 중복을 제거하고 오름차순으로 정렬한 배열의 인덱스가 곧 압축 좌표 값이 된다.

ex) 324, 12, 2100, 100, 100, 30   =정렬, 중복 제거=>   12, 30, 100, 324, 2100    =인덱스=>    0, 1, 2, 3, 4

 

1. 그렇게 구한 압축 좌표값을 value, 원래 좌표값을 key로 하는 딕셔너리에 저장하고

2. 처음에 입력받은 좌표 배열을 순회하며 각 값을 key로 하는 value를 출력하면 된다.

 

좌표가 1,000,000개 주어지기 때문에 시간초과 당하지 않으려면 이중 for문을 쓰지 않아야 한다.

// 좌표 압축
int N = int.Parse(Console.ReadLine());
int[] inputArr = Array.ConvertAll(Console.ReadLine().Split(" "), int.Parse);
int[] valueArr = inputArr.Distinct().ToArray(); // 입력된 수 중복 제거
Array.Sort(valueArr);   // 입력된 수 정렬
Dictionary<int, int> dict = new Dictionary<int, int>();

// 딕셔너리의 키로 압축 전의 수를, 값으로 정렬된 배열의 인덱스를 저장한다.
int index = 0;
foreach(int value in valueArr) {
    dict[value] = index;
    index++;
}            

// 출력은 입력 배열을 순회하면서 입력배열의 값을 딕셔너리의 키로 써서 
// 압축된 값을 출력하게 하는 방법을 쓴다.
using (var print = new StreamWriter(Console.OpenStandardOutput())) {
    for (int i = 0; i < N; i++) 
        print.Write($"{dict[inputArr[i]]} ");
}

---