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
