[백준] 18870번. 좌표 압축(JAVA)

문제

https://www.acmicpc.net/problem/18870

---

풀이(22분)

import java.io.*;
import java.util.*;
public class Main {

    static int[] originArr;
    static Set<Integer> sortedSet = new TreeSet<>();
    static int[] answerArr;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        originArr = new int[n];
        answerArr = new int[n];


        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n; i++){
            originArr[i] = Integer.parseInt(st.nextToken()); // 원본 배열 입력 받음
            sortedSet.add(originArr[i]); // 원본 입력받음과 동시에 중복 검사
        }

        int arrIdx = 0;
        Map<Integer, Integer> map = new HashMap<>(); // 값을 저장해둘 맵
        for(Integer i : sortedSet){
            map.put(i, arrIdx); // 값에 대해 인덱스 값을 하나씩 증가시키면서 키-밸류로 저장해둠.
            arrIdx++;

        }
        for(int i = 0 ; i < n; i++){
            answerArr[i] = map.get(originArr[i]);
        }

        StringBuilder sb = new StringBuilder(); // 스트링 빌더를 활용한 출력
        for(int i : answerArr){
            sb.append(i + " ");
        }

        System.out.println(sb);
    }

}

 

초기 아이디어는 이진탐색을 통해 진행하려고 했으나 맵을 사용하면 될 것을 매번 탐색하는 것을 효율적이지 않다고 생각했다.

 

최종적으로 원본 배열을 TreeSet을 통해 중복성을 제거하며 정렬을 보장받아 저장해둔다. 이에 맞춰 맵에 키 - 밸류로 값 - 인덱스값(앞에 얼마나 값이 있는지) 를 저장해둔다. 이를 정답배열에 넣어두고 출력한다.