백준18870번 문제

문제 : 좌표 압축

문제 설명 :

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

코드 :

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_18870 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] cnt= new int[N];
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        int same=0;

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i!=j && arr[i]>arr[j]){
                    for(int k=0;k<j;k++){
                        if(arr[j]==arr[k]) same++;
                    }
                    if(same==0) cnt[i]++;
                    same=0;
                }
            }
        }
        for(int i=0;i<N;i++){
            System.out.print(cnt[i] +" ");
        }
    }
}

처음 이런식으로 접근해 3중 for문을 사용했는데 당연히 시간초과,,그러고 찾아본 방법이 hashmap,, 근데 이것도 시간초과 그 결과 StringBuilder를 사용해야한다는 것을 알고 다시 접근.

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_18870 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] arrclone = new int[N];
        int cnt=0;
        HashMap map = new HashMap<>();
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        arrclone = arr.clone();
        Arrays.sort(arrclone);
        for(int i=0;i<N;i++){
            if(!map.containsKey(arrclone[i])) map.put(arrclone[i],cnt++);
        }
        for (int i = 0; i < arr.length; i++) {
            sb.append(map.get(arr[i])).append(" ");
        }
        System.out.println(sb);
    }
}

문제 풀이:

하나의 clone배열을 더 만들어 배열을 복사한 후 정렬한다.

for(int i=0;i<N;i++){
            if(!map.containsKey(arrclone[i])) map.put(arrclone[i],cnt++);
        }

그 후 위의 코드와 같이 각 배열의 값을 key값으로 하고 중복되지 않는다면 cnt++을 통해 등수를 메긴다. 쉽게 말해 오름차순으로 정렬 후 각 해당 값들에 등수를 메겨 가장 작은 값은 0, 그 다음은 1 이런식으로 등수를 메긴다.

참조: https://hacktiming.tistory.com/34