[백준 - 18870] 좌표 압축 .java

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

 

 

• 자신 보다 작은 수들 중에 서로 다른 수의 개수를 세면된다
• 중복인 경우면 1번만 카운트한다

=> 입력 받은 순서가 기준이 되어야함

=> 입력 받을 때, 좌표와 함께 인덱스도 같이 저장 [값][인덱스]

 

• 값을 기준으로 정렬하기 위해 정렬 기준 재설정해준다
• 오름차순으로 되면 0번에 위치하면 자신보다 작은 값이 없기에 답은 0이다
• 정렬순으로중복을 만날땐 카운트하지 않아야한다 -> 현재와 바로 다음 숫자 비교
• 정답 배열은 함께 저정되어있는 인덱스 값으로 저장한다

2차원 배열을 이용해서 한번에 저장하고, 답이 누적으로 카운트되는 점을 이용하는 점이 어려웠다

 

 

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;


public class test1 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        //현재 인덱스를 값과 함께 저장
        int[][] nums = new int[n][2];
        for(int i = 0; i < n; i++){
            nums[i][0] = sc.nextInt();
            nums[i][1] = i;
        }

        Arrays.sort(nums, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];//값을 기준으로 오름차순 정렬
            }
        });

        int[] result = new int[n];

        //정렬된 이후 처음 값은 자신보다 작은 값이 없음
        int ind=0;
        result[nums[0][1]] = ind;

        //중복 제거하면서 세기
        for(int i =1;i<n;i++){
            if(nums[i][0] != nums[i-1][0]) ind++;
            result[nums[i][1]] = ind;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < n; i++){
            bw.write(result[i]+ " ");
        }
        bw.flush();

    }
}

 

 

다른 풀이 - Set, Map

• TreeSet -> 중복 제거 + 작은 순으로 자동 정렬
• Map으로 현재 값과 그 값의 압축된 좌표값을 동시에 저장
• nums 순회하여 현재 좌표가 가지는 압축된 좌표값을 출력

 

 

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;


public class test1 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        //입력된 좌표를 작은 순으로 정렬, 중복제거 -> tree
        int[] nums = new int[n];
        Set<Integer> set = new TreeSet<>();
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            set.add(nums[i]);
        }

        //작은 순서대로 0번 인덱스 부여
        Map<Integer, Integer> sorted = new HashMap<>();
        int idx = 0;
        for(int x : set){
            sorted.put(x, idx++);
        }


        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < n; i++){
            bw.write(sorted.get(nums[i])+ " ");
        }
        bw.flush();

    }
}