[백준] 11870 좌표 압축(자바)

문제를 설명하면

수직선 위에 좌표 x1, x2, ... xN이 있는데 좌표에 좌표압축을 적용하려고 한다

첫번째줄에는 N이 주어지고 두번째줄에는 x1, x2, ... xN이 주어진다

 

이 문제도 꽤 오래걸렸다

시간초과문제로 계속 틀렸다

일단 full code는 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int[] sorted = Arrays.stream(a).distinct().sorted().toArray();

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(a[i])).append(' ');
        }
        System.out.println(sb);
    }
}

 

처음부터 보면

 

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = sc.nextInt();
}
sc.close();

 

스캐너를 sc로 생성하고

정수 n을 읽어오고

int 배열 a를 생성하고 n개의 정수를 입력받아서 배열 a에 차례대로 저장한다

하도 시간초과 시간초과 해서 sc를 닫았다

 

int[] sorted = Arrays.stream(a).distinct().sorted().toArray();

 

다른 방법을 시도해도 안돼서 스트림을 썼다

이번에 처음 써봤다

array에서 stream으로 바꾸고 distinct()로 중복제거하고 sorted로 오름차순 정렬하고

toArray()로 정렬된 요소들을 다시 배열로 변환해서 int[] sorted 에 저장한다

 

HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < sorted.length; i++) {
    map.put(sorted[i], i);
}

 

배열 a에 저장되어있던 각각의 요소를 sorted의 인덱스에 매핑하기 위해

HashMap map을 생성하고

sorted 길이만큼 반복하여 각 요소를 키로하여 map에 추가하고 값은 sorted 각 요소의 인덱스로 한다

 

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(map.get(a[i])).append(' ');
}
System.out.println(sb);

 

StringBuilder sb를 생성해서 출력 문자열을 만들었다

n번 반복하여 map을 사용해서 get으로 a의 요소를 호출해서 이에 해당하는 값(인덱스)를 가져와서

한칸 띄워서 sb에 추가한다

sb를 출력한다