좌표 압축
| 2 초 | 512 MB | 119386 | 51254 | 38350 | 40.100% |
문제
수직선 위에 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
- -109 ≤ Xi ≤ 109
예제 입력 1 복사
5
2 4 -10 4 -9
예제 출력 1 복사
2 3 0 3 1
예제 입력 2 복사
6
1000 999 1000 999 1000 999
예제 출력 2 복사
1 0 1 0 1 0
좌표 압축 이거 뭔 소리지
문제가 이해가 안 되네 정말
진짜 이해가 안 되서 문제 풀기 보류
어제 여기까지 써놓고 다음 날인 오늘 보니까 이해돼서 풀기로
근까 좌표 X들을 입력을 받고! 그 숫자보다 더 작은 애들 개수를 X'에 넣는 거다.
예제 1을 봤을 때 2보다 작은 숫자는 -9, -10이다. 그러니까 X'에 2가 들어간다. 4보다 작은 숫자는 2, -9, -10 이라 3, -10보다 작은 수는 없으므로 0, -9보다 작은 수는 -10 한 개로 1
막 생각나는 건 X를 입력 받고 입력받은 X 배열과 동일하게 Y 배열을 만들고 X 배열을 정렬시킨 후 Y 배열의 숫자랑 비교해서 같은 숫자가 나오면 종료 후 Y 인덱스에 그 인덱스 넣기... 인데 이중반복문이라 뭔가 시간초과 날 것 같다.
아 잠만 서로 다른 숫자네 밑에 2번 예제에서는 1 0 1 0 1 0 나오네... ArrayList 해야 하나 아니면 Set?? 선언 어떻게 하더라.. 근데 Set이 순서가 없지 않았나... ??
ArrayList로 구현했다. contains() 사용해서 중복 아닐 때만 더해주는 걸로..
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int[] X = new int[N];
ArrayList<Integer> Y = new ArrayList<>();
for (int i = 0; i < N; i++) {
X[i] = Integer.parseInt(st.nextToken());
if (!Y.contains(X[i])) {
Y.add(X[i]);
}
}
Collections.sort(Y);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
int j = 0;
while (X[i] != Y.get(j)) {
j++;
}
sb.append(j).append(" ");
}
System.out.println(sb);
}
}
역시 이중 반복문이 문제인 것 같다...
- 1 ≤ N ≤ 1,000,000
- -109 ≤ Xi ≤ 109
이 숫자를 보아하니... 이중 반복문이 문제 같다!!
라고 생각했는데 내가 예제 1로 돌려봤는데도 오류 났다.
보니까 입력을 제대로 못 받고 있었다... StringTokenizer가 왜 위에 있고 N은 왜 저렇게 됐지 ㅎ
일단 다시 돌려봐야지
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] X = new int[N];
ArrayList<Integer> Y = new ArrayList<>();
for (int i = 0; i < N; i++) {
X[i] = Integer.parseInt(st.nextToken());
if (!Y.contains(X[i])) {
Y.add(X[i]);
}
}
Collections.sort(Y);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
int j = 0;
while (X[i] != Y.get(j)) {
j++;
}
sb.append(j).append(" ");
}
System.out.println(sb);
}
}
이번엔 진짜 이중 반복문이 문제...
문득 ArrayList의 indexOf 가 생각나서 그걸로 바꿨다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] X = new int[N];
ArrayList<Integer> Y = new ArrayList<>();
for (int i = 0; i < N; i++) {
X[i] = Integer.parseInt(st.nextToken());
if (!Y.contains(X[i])) {
Y.add(X[i]);
}
}
Collections.sort(Y);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(Y.indexOf(X[i])).append(" ");
}
System.out.println(sb);
}
}
????????
뭔.데.
내가 다 해줫잔아... 내가 다 해줬잔하ㅏ 뭐가 부족한데?????? 어?????????????
N 길이가 개길어서 저거 다 확인하면 시간 초과 되는 건가???
아무리 봐도 모르겠어서 지피티에게 헬프 쳤다.
좋은 질문입니다. 이 코드가 시간 초과가 나는 이유는 바로 이 부분 때문입니다:
sb.append(Y.indexOf(X[i])).append(" ");
이 Y.indexOf(X[i])는 리스트를 앞에서부터 순차적으로 검색하기 때문에, **O(N)**의 시간이 걸립니다. 전체 N개의 좌표에 대해 이 연산을 수행하므로, 전체 시간 복잡도는 **O(N^2)**이 됩니다.
👉 이건 최대 N = 1,000,000인 입력에 대해서는 너무 느립니다.
세상에나... 이중 for문이랑 똑같은 거였다...
해쉬맵을 쓰란다 아 맞네 나중에 key로 꺼내올 수 있네
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] X = new int[N];
for (int i = 0; i < N; i++) {
X[i] = Integer.parseInt(st.nextToken());
}
int[] sorted = X.clone();
Arrays.sort(sorted);
Map<Integer, Integer> map = new HashMap<>();
int idx = 0;
for (int num : sorted) {
if (!map.containsKey(num)) {
map.put(num, idx++);
}
}
StringBuilder sb = new StringBuilder();
for (int num : X) {
sb.append(map.get(num)).append(" ");
}
System.out.println(sb);
}
}
오케
💡 핵심 포인트 요약
| Y.indexOf(X[i]) | 리스트를 순차 탐색하므로 느림 → O(N^2) |
| 개선 방법 | Map에 미리 인덱스를 저장하고 조회 → O(N log N) |
| 정렬 | 중복 제거를 위해 정렬 필요 (Arrays.sort → O(N log N)) |
| 전체 시간복잡도 | O(N log N)으로 줄어듦 |
내가 해결법이라고 생각했던 indexOf는 어차피 걔가 안에서 순차 탐색을 하고 있으므로 O(N^2) 였다..
그러면 언제 해쉬맵을 써야 한다고 딱!! 판단이 올라나?
✅ HashMap이 빛을 발하는 대표적인 경우들
1. 좌표 압축 (이번 문제)
- 원소의 상대적 순위를 구할 때 (값을 작은 수로 압축)
- ✔ 정렬 + 중복 제거 후, 값 → 인덱스 매핑
2. 두 수의 합 (Two Sum)
배열에서 두 수를 더해서 특정 합이 되는 쌍을 찾는 문제
// 주어진 배열에서 두 수를 더해서 target이 되는 인덱스 쌍 반환
int[] nums = {2, 7, 11, 15}; int target = 9;- ✔ HashMap에 값 → 인덱스로 저장해두고, target - 현재 값이 존재하는지 빠르게 찾음
3. 문자/숫자 빈도 세기 (Frequency Counter)
- ✔ HashMap으로 등장 횟수 세기
예시 문제:
- 문자열이 애너그램인지 판단
- 가장 많이 등장한 문자/숫자 구하기
4. 중복 탐지 / 빠른 존재 확인
- ✔ 값이 등장했는지 빠르게 확인할 때
- HashSet처럼 존재 여부만 판단할 때도 자주 사용
5. 누적합 + 해시맵
- 특정 누적합이 몇 번 나왔는지 기억해 두었다가 패턴 찾기
- ✔ 예: 부분 배열의 합이 특정 값이 되는 경우의 수
6. DFS/BFS 방문 여부 기록
- 노드가 숫자나 문자, 튜플처럼 복잡한 형태일 때
- ✔ 방문한 상태 → true/false를 Map으로 기록
🔍 정리: 언제 HashMap 쓸까?
| 값의 순위를 매겨야 할 때 | 값 → 순위 저장 |
| 빠르게 특정 값을 찾고 싶을 때 | 값 → 인덱스 or 존재 여부 저장 |
| 값의 등장 횟수를 세야 할 때 | 값 → 빈도 저장 |
| 복잡한 상태 저장해야 할 때 | 상태 → 값 저장 |
그러니까 존재 여부/중복 탐지 이럴 때 좋다는 것 같다... 앞으로 잘 써봐야지
코드에 주석도 달아봤다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // N 입력
StringTokenizer st = new StringTokenizer(br.readLine()); // 좌표들 입력
int[] X = new int[N]; // 배열 생성
for (int i = 0; i < N; i++) {
X[i] = Integer.parseInt(st.nextToken());
} // 좌표 배열에 넣어주기
int[] sorted = X.clone(); // X 정렬해서 담아줄 새로운 배열
Arrays.sort(sorted); // 새로운 배열 정렬해주기
Map<Integer, Integer> map = new HashMap<>(); // 해쉬맵 생성
int idx = 0; // 중복 없앤 인덱스 번호
for (int num : sorted) {
if (!map.containsKey(num)) {
map.put(num, idx++);
} // 맵에 키(숫자) 없을 때만 맵에 숫자랑 인덱스 같이 넣어줌. 숫자 하나 넣을 때마다 인덱스 1씩 증가
}
StringBuilder sb = new StringBuilder(); // 결과 담아줄 스트링빌더
for (int num : X) {
sb.append(map.get(num)).append(" ");
} // 배열 X를 돌면서 map에서 키 값인 num으로 idx를 꺼내오고 sb에 append 해준다
System.out.println(sb); // 출력
}
}
'백준 풀기' 카테고리의 다른 글
| 백준 2606번: 바이러스 with Java (0) | 2025.05.04 |
|---|---|
| 백준 1431번: 시리얼 번호 with Java (0) | 2025.04.24 |
| 백준 17478번: 재귀함수가 뭔가요? with Java (0) | 2025.04.21 |
| 백준 11866번: 요세푸스 문제 0 with Java (0) | 2025.04.20 |
| 백준 10866번: 덱 with Java (0) | 2025.04.20 |