수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
int n=Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq=new PriorityQueue<>();
int[] array=new int[n];
String s=br.readLine();
StringTokenizer st=new StringTokenizer(s);
for(int i=0; i<n; i++) {
array[i] = Integer.parseInt(st.nextToken());
pq.add(array[i]);
}
int[] sorted=new int[n];
int previous=pq.remove();
sorted[0]=previous;
int index=1;
for(int i=1; i<n; i++){
int temp=pq.remove();
if(previous==temp)
continue;
else
sorted[index++]=temp;
previous=temp;
}
for(int i=0; i<n; i++)
bw.write(Arrays.binarySearch(sorted, 0, index, array[i])+" ");
bw.flush();
}
}
Counting Sort를 사용하면 좋겠지만 수의 범위가 약 20억이라서 Scanner로 처음의 배열을 만들고 Heap Sort를 사용해서 중복된 수는 제거하면서 새로운 정렬된 배열을 만들어준 뒤에, 처음의 배열에서 각각의 요소를 정렬된 새 배열에서 Binary Search 했다. 그 인덱스가 정답이기 때문에 바로 출력해줬다.
시간 초과(혹시나 싶어서 Scanner 대신 BufferedReader, BufferedWriter로 바꿨다)
😁