[문제]
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > 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
[예제]
>문제 풀이
정렬하는 방법과 hashmap 사용할 줄만 알면 쉬운 문제였다.
(근데 hashmap 딱 한번 써보고 안써서 까먹어서 다시 찾아봄..ㅎㅎ;)
<로직>
- N, arr[] 입력 받고
- arr_v= arr.clone(); // arr_v[] 배열에다가 깊은 복사로 붙여넣는다.
- arr.sort
- N만큼 반복문을 돌리며
: arr값을 중복되지 않게 hashmap에 넣는다. - N만큼 반복문을 돌리며
: StringBuilder sb에다가 hashmap에서 키값이 arr_v인 value를 붙여준다.(append) - sb.toString()을 출력한다.
>전체 코드
import java.util.*;
public class Main {
public static void main(String [] args) {
int N, before, arr[], arr_v[];
Scanner scan= new Scanner(System.in);
//입력받기
N= scan.nextInt();
arr= new int[N];
arr_v= new int[N];
HashMap<Integer, Integer> map= new HashMap<>();
for(int i=0; i<N; i++) {
arr[i]= scan.nextInt();
}
arr_v= arr.clone(); //arr를 arr_v로 (깊은)복사
Arrays.sort(arr); //정렬
before= (int)Math.pow(10, 9)+1;
for(int i=0, j=0; i<N; i++) {
if(before!=arr[i]) { //중복아닌 값만
map.put(arr[i], j++);//map에 저장
before=arr[i];
}
}
StringBuilder sb= new StringBuilder();
for(int i=0; i<N; i++) {
sb.append(map.get(arr_v[i])+" "); //arr_v값을 키로 가진 map을 get
}
System.out.println(sb.toString()); //출력~~
}//end
}https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]3036번: 링_Java (0) | 2021.05.27 |
|---|---|
| [백준 알고리즘]14495번: 피보나치 비스무리한 수열 (1) | 2021.05.25 |
| [백준 알고리즘]14503번: 로봇 청소기_Java (0) | 2021.05.22 |
| [백준 알고리즘] 2573번: 빙산(BFS)_Java (0) | 2021.05.19 |
| [백준 알고리즘]2468번: 안전 영역(BFS)_Java (0) | 2021.05.19 |
