[백준] 18870 좌표 압축.java
문제
수직선 위에 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
나의 풀이
- 배열을 두개를 n개의 길이만큼 생성한다음 두개의 배열에 모두 동일하게 입력을 받는다.
- 그 후 1번 배열은 Arrays.sort() 를 사용해서 정렬을 해주고,
- 중복이 안되게 해주는 map에 key와 value를 넣어줄건데 key는 배열의 값, value는 rank(몇번째로 큰지)를 넣어주면 된다.
- 그 후 2번 째 배열과 map을 비교해서 2번째 배열에 해당하는 값을 key와 비교해서 value값을
- StringBuilder에 더해주면 시간초과도 피해서 출력할 수 있다.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n]; //정렬용
int[] answer = new int[n]; //map이랑 비교할 배열용
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//배열 입력받기
for (int i = 0; i < n; i++) {
arr[i] = answer[i] = sc.nextInt();
}
//배열 오름차순 정렬
Arrays.sort(arr);
//-10 -9 2 4 4
// 0 1 2 3 3
int rank = 0;
for (int i : arr) {
if (!map.containsKey(i)) {
map.put(i, rank);
rank++;
}
}
StringBuilder sb = new StringBuilder();
for (int key : answer) {
sb.append(map.get(key)).append(" ");
}
System.out.println(sb);
}
}
Author And Source
이 문제에 관하여([백준] 18870 좌표 압축.java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@moon960427/백준-18870-좌표-압축.java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)