BOJ - 18870 좌표 압축

leehyunjon·2022년 5월 27일

boj 이분탐색 정렬

Algorithm

목록 보기

48/162

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

Problem

Solve

해당 문제는 Map을 이용하여 중복을 제거하여 압축 결과를 반환하는 방법과 이분 탐색을 이용해서 압축 결과를 반환하는 방법 두가지가 있다.

Map을 이용한 풀이

좌표 압축의 결과는 Xi>Xj를 만족하는 중복을 제외한 Xj의 개수이므로 좌표리스트를 오름차순으로 새로운 배열에 기존 좌표리스트를 정렬한다.
정렬된 좌표 리스트를 돌면서 Map에 존재하지 않는 좌표에 rank로 value값을 넣어준다(O(N)). 그렇게 되면 Map에는 좌표에 0부터 오름차순으로 rank가 저장되어있다.

예를 들어 {-10,-9,2,4,4}의 좌표들이 있다면 {{-10,0},{-9,1},{2,2},{4,3}}으로 저장되어있게된다.

그 후 기존 좌표 리스트를 돌면서 각 좌표값을 Map에서 찾아 O(1)으로 좌표보다 작은 좌표의 개수를 반환할수 있게 된다.

이분탐색을 이용한 풀이

좌표를 입력받을때 배열 초기화와 Set을 이용해 중복이 제외된 좌표를 초기화한다.

Set을 중복을 제외한 좌표 배열로 변환한 후 정렬한다.

기존 좌표 배열을 돌면서(O(N)) 각 좌표를 target으로 놓고 중복 제외한 좌표 배열에서 이분 탐색을 통해 해당 좌표 위치를 반환(O(longN))하면 반환된 값이 중복을 제외한 Xj의 개수이다.

Code

Map을 이용한 풀이

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		//기존 좌표 배열
        arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

		HashMap<Integer, Integer> map = new HashMap<>();

		//정렬을 위한 깊은 복사
		arr2 = arr.clone();
		Arrays.sort(arr2);

		int rank=0;
        //각 좌표의 rank 설정
		for(int i=0;i<arr2.length;i++){
			int num = arr2[i];
			if(!map.containsKey(num)){
				map.put(num, rank);
				rank++;
			}
		}

		StringBuilder sb = new StringBuilder();
        //좌표배열의 순서대로 좌표 압축 결과 반환
		for(int target : arr){
			sb.append(map.get(target));
			sb.append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

이분탐색을 이용한 풀이

static int N;
	static int[] arr;
	static int[] arr2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
        //기존 좌표 배열
		arr = new int[N];
        //중복 제거된 좌표
		HashSet<Integer> set = new HashSet<>();
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //기존 좌표 배열과 Set 초기화
		for(int i=0;i<N;i++){
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			set.add(num);
		}

		//중복 제거된 좌표들을 배열화
		arr2 = new int[set.size()];
		int i=0;
		for(int num : set){
			arr2[i++] = num;
		}
		Arrays.sort(arr2);

		StringBuilder sb = new StringBuilder();
        //기존 좌표배열의 좌표를 target으로 binary_search
		for(int num : arr){
			int result = binarySearch(num);
			sb.append(result);
			sb.append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//중복 제거된 좌표로 binary_search
	static int binarySearch(int target){
		int start=0;
		int end=arr2.length-1;

		while(start<=end){
			int mid = (start+end)/2;

			if(arr2[mid]>target){
				end = mid-1;
			}else if(arr2[mid]<target){
				start = mid+1;
			}else{
				return mid;
			}
		}
        //기존 배열에 무조건 포함되어있는 좌표들이기 때문에 필요없는 값
		return -1;
	}