백준 알고리즘 문제(87) - 좌표 압축

좌표 압축에 대해 알아보자.
주어진 문제는 주어진 입력들 사이에서 스스로보다 작은 값들의 개수를 출력해야한다.
ex)
5
2 4 -10 4 -9
출력
2 3 0 3 1

여러가지 방법을 적용해보겠다.

countingsort는 1,000,000,000 만큼의 배열을 생성해줘야 하므로, 메모리낭비 방지를 위해 하지않겠다.
검증해야할 범위가 너무 넓어서 제출에도 긴 시간이 걸린다.

1. 배열에 저장한 후에 반복문으로 count 변수를 통해 값을 올려줄 수 있다.

이 경우에는 시간복잡도도 상당히 효율이 떨어지고, 시간초과에 걸린다. O(n^2) 급의 정렬은 모두 시간초과에 걸릴 수 밖에 없는 문제다. 그리고 중복을 체크할 수 없다. 그리고 두 번째 답안에서 3 0 3 0 3 0의 답이 나온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		
		int[] arr = new int[N];
		
		for(int i =0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		StringBuilder sb = new StringBuilder();
		int count =0;
		for(int i =0; i<arr.length; i++) {
			count =0;
			for(int j =0; j<arr.length; j++) {
				if(arr[i] > arr[j] && i !=j) {
					count ++;
				}
			}
			if(i==arr.length-1) {
				sb.append(count);
			} else {
				sb.append(count+" ");
			}
			
		}
		
	System.out.print(sb);
	}
}

2. Hashmap을 이용한 방법이다. 시간복잡도 O(nlogn)의 방법이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		int[] arr = new int[N];
		for(int i =0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] arr_sort = arr.clone();
		Arrays.sort(arr_sort);
		
        
		Map<Integer, Integer> map = new HashMap<>();
		int idx = 0;
		for(int n : arr_sort)
			if(!map.containsKey(n))
				map.put(n, idx++);
		
		StringBuilder sb = new StringBuilder();
		for(int n : arr)
			sb.append(map.get(n)).append(' ');
		
		System.out.println(sb.toString());
	}
}

해쉬맵은 배열에 index대신 Key값을 입력하게 해주는 메소드다. 숫자만이 아니라 소문자나 대문자도 숫자로 변환해준다.

map.containKey 메소드는 arr_sort(클론)이 정렬된 상태에서 같은게 있을 시에 true값, 없을시에 false 값을 받는다.

put은 말그대로 n을 key값으로하는 배열을 추가하고, idx라는 value를 카운트로써 증가시켜준다.

그리고 get에서 arr를 map.get으로 가져오는 이유는 arr_sort를 clone으로 사용해서 임의적으로 value 값의 순서를 바꿔줬기 때문에, 원래 순서가 저장된 arr를 가져온 것이다.