문제 설명
수직선 위에 N개의 좌표가 주어질 때,
각 좌표를 좌표 압축한 값을 구하는 문제이다.
좌표 압축의 정의는 다음과 같다.
Xi > Xj 를 만족하는 서로 다른 Xj의 개수즉, 어떤 값보다 작은 값들의 개수를 구하면 된다.
입력
첫째 줄
N좌표 개수
둘째 줄
X1 X2 X3 ... XN조건
1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9출력
좌표 압축 결과
X'1 X'2 X'3 ... X'N입력 예시
5
2 4 -10 4 -9출력 예시
2 3 0 3 1문제 해결 아이디어
이 문제의 핵심은 다음이다.
값의 순서를 유지하면서
작은 값들의 개수를 빠르게 계산즉,
정렬 + 중복 제거 + 인덱스 매핑문제이다.
내가 작성한 코드
나는 배열을 복사한 뒤 정렬하고,
Map을 이용해 값 → 압축값을 저장했다.
코드
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
int[] sorted = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
sorted[i] = arr[i];
}
Arrays.sort(sorted);
Map<Integer, Integer> map = new HashMap<>();
int idx = 0;
for (int i = 0; i < N; i++) {
if (!map.containsKey(sorted[i])) {
map.put(sorted[i], idx++);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(map.get(arr[i])).append(" ");
}
System.out.println(sb);
}
}강의 코드 (정렬 + 인덱스 방식)
강의에서는 값과 원래 인덱스를 함께 저장한 뒤
정렬 후 압축값을 직접 계산했다.
코드
import java.io.*;
import java.util.*;
class Main
{
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
int[][] xs = new int[N][2];
for (int i = 0; i < N; i++) {
xs[i][0] = Integer.parseInt(inputs[i]);
xs[i][1] = i;
}
Arrays.sort(xs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int[] ans = new int[N];
int idx = 0;
ans[xs[0][1]] = idx;
for (int i = 1; i < N; i++) {
if (xs[i][0] != xs[i - 1][0]) idx++;
ans[xs[i][1]] = idx;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < N; i++)
bw.write(ans[i] + " ");
bw.flush();
}
}강의 코드 (Map + TreeSet 방식)
또 다른 방식은 TreeSet을 이용한 정렬 + Map 매핑이다.
코드
import java.io.*;
import java.util.*;
class Main
{
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
int[] xs = new int[N];
Set<Integer> setX = new TreeSet<>();
for (int i = 0; i < N; i++) {
xs[i] = Integer.parseInt(inputs[i]);
setX.add(xs[i]);
}
Map<Integer, Integer> sortedIndex = new HashMap<>();
int idx = 0;
for (int x : setX)
sortedIndex.put(x, idx++);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < N; i++)
bw.write(sortedIndex.get(xs[i]) + " ");
bw.flush();
}
}내 코드 vs 강의 코드 비교
1. 접근 방식 차이
내 코드
배열 복사 → 정렬 → Map으로 매핑강의 코드 (정렬 방식)
값 + 인덱스 저장 → 정렬 → 압축값 계산강의 코드 (TreeSet 방식)
Set으로 중복 제거 + 정렬 → Map 매핑2. 핵심 차이
| 방식 | 특징 |
|---|---|
| 내 코드 | Map 기반 좌표 압축 |
| 강의 코드1 | 정렬 + 인덱스 추적 |
| 강의 코드2 | TreeSet + Map |
3. 성능 차이
내 코드
정렬: O(N log N)
Map: O(N)→ 전체
O(N log N)강의 코드 (정렬)
정렬 + 배열 접근→ 역시
O(N log N)강의 코드 (TreeSet)
TreeSet 삽입: O(log N)→ 전체
O(N log N)4. 중요한 차이 포인트
내 코드
if (!map.containsKey(sorted[i]))→ 중복 제거를 직접 처리
강의 코드
if (xs[i][0] != xs[i - 1][0])→ 정렬 후 비교로 처리
강의 코드2
TreeSet→ 자동으로 정렬 + 중복 제거
핵심 개념
1. 좌표 압축
값의 순위를 구하는 문제2. 정렬 활용
정렬 → 순서 → 인덱스 부여3. 중복 제거
방법 3가지
1. Map containsKey
2. 정렬 후 비교
3. Set 사용4. Map 매핑
value → compressed index시간 복잡도
O(N log N)- 정렬이 핵심
정리
이 문제는 단순 정렬 문제가 아니라
값을 순위로 변환하는 좌표 압축 문제였다.
내 코드는 Map을 활용해 직관적으로 구현했고,
강의 코드는 다양한 방식으로 해결 방법을 보여주었다.
핵심 차이는 다음과 같다.
내 코드 → Map 중심 접근
강의 코드 → 정렬 중심 접근결국 어떤 방식이든
정렬 + 중복 제거 + 인덱스 매핑이 3가지가 핵심이다.
이 문제를 통해
좌표 압축은 정렬 기반 문제라는 것을 이해할 수 있었다.
아는거 없는 전공자