BOJ - 좌표 압축

leehyunjon·2022년 12월 9일
0

Algorithm

목록 보기
140/162

18870 좌표압축 : https://www.acmicpc.net/problem/18870


Problem


Solve

Map을 이용한 방식과 BinarySearch 두가지 방법을 이용하여 풀이를 해보았습니다.

첫번째 풀이 - Map

주어진 숫자들을 정렬을 수행하고 이전에 있는 값과 비교하여 이전값보다 크다면 배열의 크기를 +1씩 증가시켜주는 누적합을 사용하였습니다. 그리고 각 배열이 가지는 개수를 Map에 저장하였습니다.

int[] subArr = new int[N];	//정렬된 숫자 배열
int[] prefixSumArr = new int[N];	//subArr이 가지는 값의 누적합

...
        
Map<Integer, Integer> map = new HashMap<>();	//주어진 숫자보다 작은 개수를 저장한 map
Arrays.sort(subArr);

map.put(subArr[0],0);	//정렬된 숫자의 첫번째값보다 작은 값은 없기 때문에 0으로 저장

//이전값보다 큰 경우에만 이전값의 개수에 +1로 증가 후 map에 저장
for(int i=1;i<N;i++){
	if(subArr[i-1]<subArr[i]) prefixSumArr[i] = prefixSumArr[i-1]+1;
	else prefixSumArr[i] = prefixSumArr[i-1];
	map.put(subArr[i], prefixSumArr[i]);
}

Map에 중복이 제거된 값과 해당 값보다 작은 수의 개수가 저장되어있습니다.
그리고 기존에 주어진 숫자를 순서대로 map에서 찾아 개수를 반환해줍니다.


두번째 풀이 - BinarySearch

Set을 통해서 주어진 숫자의 중복을 제거해줍니다.
그리고 중복이 제거된 숫자들 토대로 배열을 만들어주고 해당 배열을 오름차순으로 정렬해줍니다.

그리고 주어진 숫자를 순차적으로 target으로 놓고 이진탐색을 통해 target보다 같거나 큰 숫자의 index값을 반환해줍니다.

이진탐색에서는 mid가 가리키는 값이 target보다 작다면 start = mid+1
mid가 가리키는 값이 target보다 같거나 크다면 end = mid로 선언합니다.
그렇게 되면 start가 가리키는 값은 항상 target보다 크거나 같은 값을 가리키게 됩니다.

2 4 -10 4 -9가 주어졌을때, Set을 통해 중복을 제거하고 오름차순으로 정렬하게 되면 -10 -9 2 4의 배열이 생성되게 됩니다.

이 배열을 가지고 이분탐색을 수행해보겠습니다.
target이 4인 경우 입니다.

mid값이 1로 -9를 가리키고 있습니다. -9는 target의 4보다 작습니다.
그렇기 때문에 start = mid+1 즉, start = 2로 이동시켜줍니다.

mid값이 2로 2를 가리키고 있습니다. 2는 target의 4보다 작습니다.
그렇기 때문에 start = mid+1로 즉, start = 3으로 이동시켜줍니다.

start==end 가 되었기 때문에 이분탐색을 중단하고 start는 3을 가리키고 있습니다.
즉 target 4보다 작은 값은 3개가 있습니다.

target이 -10인 경우를 보겠습니다.

초기 mid값이 -9를 가리키고 있고 target -10보다 크기때문에 end = mid 즉, end = 1로 이동시켜줍니다.

그리고 mid값이 -10을 가리키고 있고 target -10보다 같기때문에 end = mid 즉, end = 0으로 이동시켜줍니다.

start==end가 되고 start는 0을 가리키고 있기 때문에 target -10보다 작은 값은 0이 됩니다.


Code

첫번째 풀이 - Map

import java.io.*;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] subArr = new int[N];
        int[] prefixSumArr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            subArr[i] = arr[i];
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(subArr);
        map.put(subArr[0],0);
        for(int i=1;i<N;i++){
            if(subArr[i-1]<subArr[i]) prefixSumArr[i] = prefixSumArr[i-1]+1;
            else prefixSumArr[i] = prefixSumArr[i-1];
            map.put(subArr[i], prefixSumArr[i]);
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            sb.append(String.valueOf(map.get(arr[i]))).append(" ");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

두번째 풀이 - 이분탐색

import java.io.*;
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            set.add(arr[i]);
        }
        
        int[] nonDuplicateArr = new int[set.size()];
        int idx=0;
        for(int num : set){
            nonDuplicateArr[idx++] = num;
        }
        
        Arrays.sort(nonDuplicateArr);
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            int target = arr[i];
            int zip = binarySearch(nonDuplicateArr, target);
            sb.append(zip).append(" ");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    
    static int binarySearch(int[] nonDuplicateArr, int target){
        int start = 0;
        int end = nonDuplicateArr.length-1;
        
        while(start<end){
            int mid = (start+end)/2;
            
            if(nonDuplicateArr[mid] < target){
                start = mid+1;
            }else{
                end = mid;
            }
        }
        
        return start;
    }
}

Result


Reference

profile
내 꿈은 좋은 개발자

0개의 댓글