[B0J]좌표 압축(18870)

티어 : Sliver 2
정답여부 : 정답
알고리즘 유형 : 정렬, 값/좌표 압축
시간 제한 : 2초

💡문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

💡입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

💡출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

💡예제 입력1

5
2 4 -10 4 -9

💡예제 출력1

2 3 0 3 1

💡예제 입력2

6
1000 999 1000 999 1000 999

💡예제 출력2

1 0 1 0 1 0

💡문제 분석 요약

• 각 좌표의 값에 따라 오름차순 순서를 출력하면 되는 문제

💡알고리즘 설계

• Coordinates : 각 좌표들 입력받을 배열
• Coordinates_sort : 각 좌표 정렬 배열
• rankMap 각 좌표의 값(key)과 그 좌표 순서의 값(value)

1. 각 값을 입력받음.
2. Coordinates_sort 입력받은 좌표를 정렬
3. 각 정렬된 값을 키값에 넣어주고 rank 순위 값을 넣어주며 ++;
4. 원래 좌표 배열을 순회하면서 각 좌표의 압축된 순위를 StringBuilder에 추가

💡시간복잡도

• O(nlogn)

💡코드

import java.util.*;
import java.io.*;

public class Main{

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int Coordinates [] = new int[N];
		int Coordinates_sort [] = new int[N];
		Map<Integer, Integer> rankMap = new HashMap<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			Coordinates[i] = Integer.parseInt(st.nextToken());
			Coordinates_sort[i] = Coordinates[i];
		}
		Arrays.sort(Coordinates_sort);
		int rank = 0;
		for(int value : Coordinates_sort) {
			if(!rankMap.containsKey(value)) { // containsKey : key값이 있는지 확인
				rankMap.put(value, rank);
				rank++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int value : Coordinates) {
			sb.append(rankMap.get(value)).append(" ");
		}
		
		System.out.println(sb);
	}

}

💡 틀린 이유

이진탐색으로 풀수 있는 방법은 구글링을 통해 검색해서 문제를 다시 풀어봤다.

💡 틀린 부분 수정 or 다른 풀이

import java.io.*;
import java.util.*;

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

		int n = Integer.parseInt(bf.readLine()); // 숫자 개수
		Set<Integer> set = new HashSet<>(); // 중복제거용 set
		ArrayList<Integer> arr = new ArrayList<>(); // 정렬용 arraylist

		String[] str = bf.readLine().split(" ");
		int[] nums = new int[n]; // 기존 숫자 저장용 배열

		for (int j = 0; j < n; j++) {
			int temp = Integer.parseInt(str[j]);
			set.add(temp); 
			nums[j] = temp;
		} // 숫자 set과 배열에 저장

		for (int s : set) {
			arr.add(s); 
      	// set에 있는 숫자들 arraylist로 이동
		}

		Collections.sort(arr);

		for (int j = 0; j < n; j++) {
			bw.write(binary(arr, nums[j]) + " "); 
      	// 이진탐색하고, 숫자가 있는 위치 반환
      	// 위치 = 해당 숫자보다 작은 숫자의 수
		}

		bw.flush();
		bw.close();

	}

	public static int binary(ArrayList<Integer> a, int data) {
    // 이진 탐색
		int start = 0;
		int end = a.size();

		while (start < end) {
			int mid = (start + end) / 2; // 중간값
			if (a.get(mid) >= data) { // 찾으려는 숫자보다 같거나 크면
				end = mid; // 그 뒤의 숫자는 필요 없음
			} else { // 작으면
				start = mid + 1; // 앞의 값은 필요없음 
			}
		}

		return end; // 인덱스 값 반환
	}
}

 

💡 느낀점 or 기억할정보

뭔가 이진 탐색으로 만 풀려고 하다 보니 더 힘들었던 거 같았다. 꼭 이진탐색이 아니더라도 알고리즘을 풀어보는 방식은 여러 가지가 있으니 다양한 방면으로 접근을 해야겠다.