백준 18870 : 좌표압축 (TreeMap)

TreeMap <- 정렬된 순서로 들어오게 하는 맵

 

문제

수직선 위에 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

 

 

• 풀이

트리맵을 사용하면 TreeSet -> HashMap으로 번거롭게 두번 하는게 아닌 한번에 정렬된 상태로  맵에 넣어서 처리하는게 가능했다..

 

처음에 생각한 풀이 

1 입력받은걸 arr에 순차적으로 key형태로 저장

2 중복제거를 위해 TreeSet에 같이 저장
3  map<int, int>에 정렬된걸 넣으면서 순차적으로 0 1 2 3 4 식으로 증가
4. map.get(arr[i]) 형태로 가져온걸 stringbuilder에 저장, 출력

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        Set<Integer> set = new TreeSet<>();
        Map<Integer, Integer> mmap = new HashMap<>();
        StringTokenizer st= new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            int tmp = Integer.parseInt(st.nextToken());
            arr[i] = tmp;
            set.add(tmp);
        }

        int tmp = 0;
        for (int x : set){
            mmap.put(x, tmp++);
        }

        for (int i = 0; i < n; i++){
            sb.append(mmap.get(arr[i])).append(" ");
        }

        System.out.println(sb);
    }
}

 

- 트리맵으로 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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] input =  br.readLine().split(" ");
        TreeMap<Long, Integer> treeMap = new TreeMap<>();

        for (int i =0; i < n; i++){
            treeMap.put(Long.parseLong(input[i]),0);
        }

        int idx = 0;
        for (Map.Entry<Long, Integer> x : treeMap.entrySet()){
            Long x1 = x.getKey();
            treeMap.put(x1,idx++);
        }
        for (int i = 0; i < n; i++){
            bw.write(treeMap.get(Long.parseLong(input[i])) + " ");
        }
        bw.flush();
    }
}