[JAVA / 자바] 백준 18870번 - 좌표 압축 (실버 2)

 문제 

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

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

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

---

 입력 

첫째 줄에 N이 주어진다.

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

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

 출력 

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

---

---

 문제 접근 방법 

이번 문제는 입력된 수의 크기 순위를 0부터 매겨 수를 압축하여 출력하는 문제이다. 따라서, 숫자를 정렬하여 해당 숫자가 입력된 수 중에서 몇 번째로 큰 숫자인지 알아야 한다.

 

1. 입력을 저장할 배열을 선언해준다.

2. 입력된 수를 정렬하여 해당 수가 몇 번째 숫자인지 지정해주어야 하는데, 입력을 저장한 배열을 바꾸면 안 되기 때문에(∵ 출력 때 입력된 순서에 대응하는 압축 숫자를 해당 자리에 출력해야 하기 때문에 입력 순서를 기억해야 한다.) 입력된 수를 정렬할 배열을 선언하여 수를. clone() 함수를 통해 깊은 배열 복사를 해주고, Arrays.sort();를 통해 배열을 오름차순으로 정렬해준다.

3. 정렬된 숫자를 인덱스 0부터 끝까지 순회하면서 숫자가 달라질 때마다 0에서부터 숫자를 +1해 주면서 HashMap에 해당 숫자가 몇 번째로 큰 숫자인지 저장해준다.(key = 숫자 : value = 몇 번째로 큰 수)

4. 입력을 저장한 배열을 순회하면서 해당 숫자를 HashMap에서 찾아 value값을 출력 포맷이 맞춰 출력해준다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

처음 문제를 풀었을 때, 연산 시간이 생각보다 너무 오래 걸려서 시간을 단축해보려고 노력을 많이 해보았다. 수를 정렬하는 배열에 중복된 수가 많아서 HashSet으로 걸러보려고도 하고 입출력 시간도 줄이려 해 보고 노력해보았지만 최초에 생각했던 방법이 내가 현재 할 수 있는 최선의 방법이었다. 더 문제를 풀어보고 지금보다 많은 지식이 쌓이면 보다 괜찮은 코드를 작성할 수 있게 되지 않을까,,?

---

 문제 원본 

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 알고리즘 분류 

• 정렬
• 값 / 좌표 압축