백준 18870번 좌표 압축 자바 java

문제

 

 

풀이

 

문제에서 압축이란?

입력받은 좌표 값을 오름차순으로 정렬했을 때의 순서를 표시하는 것 (중복 값은 제외)

 

예를 들어

2 4 -10 4 -9 입력받았다면

-10 -9 2 4 (4)

0, 1, 2, 3 (4는 중복됨으로 제외)

 

2 4 -10 4 -9 -> 2 3 0 3 1

 

배열로 값을 받은 다음

비교를 하기 위해서 깊은 배열 복사로 새로운 배열을 만들고

새로운 배열을 Arrays.sort() 함수로 오름차순 정렬을 합니다

 

순서와 중복된 값을 처리하기 위해서 hashmap을 이용해서 값을 넣고

기존에 배열에서 순서 값을 hashmap을 통해 값을 표시합니다

 

 

코드

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[] arrClone;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        arrClone = arr.clone();

        Arrays.sort(arrClone);

        for (int i = 0; i < arrClone.length; i++) {
            if (!map.containsKey(arrClone[i])) {
                map.put(arrClone[i], count++);
            }
        }

        for (int i = 0; i < arr.length; i++) {
            sb.append(map.get(arr[i])).append(" ");
        }
        
        System.out.println(sb);
    }
}

printf를 이용할 경우 시간 초과가 나서 StringBuilder를 이용해서 표시

 

조금 더 시간을 단축하는 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = new Integer(br.readLine());
        int[] arr = new int[N];
        int[] arrClone;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        arrClone = arr.clone();

        Arrays.sort(arrClone);

        for (int i = 0; i < arrClone.length; i++) {
            if (!map.containsKey(arrClone[i])) {
                map.put(arrClone[i], count++);
            }
        }

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

        System.out.println(sb);
    }
}

 

 

출처

www.acmicpc.net/problem/18870