[JAVA] 백준 18870번- 좌표 압축

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

18870번: 좌표 압축

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

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[] sortedArr = new int[n];
        int[] originArr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<n; i++){
            originArr[i]= sortedArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sortedArr);

        for(int i=0; i<n; i++){
            int cnt=0;
            for(int j=0; j<n; j++){
                if(originArr[i]>sortedArr[j]) {
                    if(j>0){
                        if(sortedArr[j]!=sortedArr[j-1]) cnt++;
                    }else cnt++;
                }
                else break;
            }
            sb.append(cnt+" ");
        }
        System.out.println(sb);
    }
}

 

처음에 떠오르는대로 이렇게 풀었다가 시간 초과 남...

 

원본 배열의 원소를 하나씩 검사할때 정렬된 배열을 이중 for문으로 돌며 자기 자신이 나올때까지 카운팅해줘서 본인보다 작은 원소들의 개수를 구하려고 했다. 

이중 for문때문에 시간 초과가 난것같다. 

 

그래서 해시맵을 사용하였다. 

 

 

 

최종 제출 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine());
        int[] originArr = new int[n];
        int[] sortedArr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            originArr[i] = sortedArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sortedArr);
        int index = 0;
        for (int x : sortedArr) {
            if (!map.containsKey(x)) {
                map.put(x, index);
                index++;
            }
        }
        for (int x : originArr) {
            sb.append(map.get(x) + " ");
        }
        System.out.println(sb);
    }
}

 

 

정렬된 배열 원소를 키로, 0부터 증가하는 index를 value로 한 해시맵을 만든다.

이 때, 원소가 중복되어 나올 때 index를 증가하게 하면 안되기 때문에 map.containsKey로 검사했다.

 

기존 배열을 돌며 map에서 해당 원소를 key로 하는 value를 찾아 차례로 출력하면 된다.