[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번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net