쌉쌀한 무화과의 개발로그

[문제]

수직선 위에 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 딱 한번 써보고 안써서 까먹어서 다시 찾아봄..ㅎㅎ;)

<로직>

1. N, arr[] 입력 받고
2. arr_v= arr.clone(); // arr_v[] 배열에다가 깊은 복사로 붙여넣는다.
3. arr.sort
4. N만큼 반복문을 돌리며
   : arr값을 중복되지 않게 hashmap에 넣는다.
5. N만큼 반복문을 돌리며
   : StringBuilder sb에다가 hashmap에서 키값이 arr_v인 value를 붙여준다.(append)
6. 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