[JAVA] BOJ(백준) - 좌표 압축 - 18870

문제내용

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

문제풀이

이문제를 보고 Comparator를 활용해 풀었는데, 알고보니 이런류의 문제를 coordinate Compression라고 알고리즘의 한분류로 구분돼 있었다. BFS처럼 푸는 방법이 따로 있는건 아니고 음... 시뮬레이션과 비슷한 종류라고 생각하면 좋을꺼같다.

 

각설하고, 이문제를 푸는 방법은 2가지가 있다.

1. Comparator를 활용한 풀이.

2. rank를 활용한 풀이.

여기서 Comparator은 다른 포스팅에서 많이 말했기 때문에 그냥 넘어가고, rank는 말그대로 순위를 매긴다는 뜻이다.

 

그럼 하나씩 알아보자.

 

Comparator활용한 풀이

1. 원본배열을 만들어준다.
2. set을 이용해 중복되는 수 제거
   중복수를 제거해주는 이유는 서로 다른 수끼리만 비교가 가능하기 때문이다.
3. 리스트에 담아주고 정렬하기.
   리스트에 중복제거된 수를 담어주고, 내림차순 정렬해준다.
   내림차순 정렬해주는 이유는 예를들어 원본배열 ori = {2,3,5,1} 이라고 할때, 내림차순 정렬을 하면
   ori = {5 , 3 , 2 , 1} 이된다. 그렇다면
   5의 입장에서 Xi>Xj가 될수 있는건 3, 2, 1 로 총 3개가 된다.
   3의 입장에선 Xi>Xj가 될수 있는건 2, 1 로 총 2개가 된다.
   2의 입장에선 Xi>Xj가 될수 있는건 1 로 총 1개가 된다.
   1의 입장에선 Xi>Xj가 될수 있는건 없으므로 총 0개가 된다.
   
   즉, {2 , 3 , 5 , 1}일때 출력해야 하는 값은  {1 , 2 , 3 , 0} 이 된다.
4. HashMap에 정렬된 수를 넣어준다.
   이때 key값은 요소값
   value값은 Xi>Xj 가될수 있는 개수를 넣어준다. -> (list.size()-1) - i
5. 원본배열에서 각 요소값이 Xi>Xj인 값들을 넣어준다.
   한마디로 map.get( 원본배열 요소값 ) 을 차례대로 출력해주면 된다.

 

rank를 이용한 풀이

1. 원본 배열 같은 요소를 가진 sub 배열을 만든다.
2. sub 배열을 오름차순 정렬해준다.
3. HashMap에 sub배열의 요소값을 넣어준다.
   HashMap을 이용해 중복값을 제거함과 동시에 rank를 매길수 있다.
   key값 = sub의 요소값 
   value값 = rank가 된다.
   
   예를들어 ori = { 1, 5, 3, 7 } , sub = { 1, 3, 5, 7 } 이라고 할때 HashMap에는 다음과 같이 들어간다.
   {key:value} -> {1:0 , 3:1 , 5:2 , 7:3}
   2번에서 오름차순 정렬을 한 이유도 이처럼 각키에 해당되는 순위를 매겨주기 위해서이다.
4. 원본 배열의 모든 요소값에 대해 map에 저장된 value값을 출력한다.
   map.get( 원본배열 요소값 );

---

코드

 Comparator

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

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());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] ori = new int[n];//원본 배열
		for(int i=0; i<n; i++) 
			ori[i] = Integer.parseInt(st.nextToken());
		
		HashSet<Integer> set = new HashSet<>();
		for(int i=0; i<n; i++)//중복제거
			set.add(ori[i]);
		
		List<Integer> list = new ArrayList<>();
		Iterator<Integer> iter = set.iterator();
		while(iter.hasNext())//리스테 담아주기
			list.add(iter.next());
		
		//내림창순 정렬
		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		});
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		//key:요소값 , value:요소값이 Xi>Xj에 해당하는 개수
		for(int i=0; i<list.size(); i++) 
			map.put(list.get(i), list.size()-i-1);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++) 
			sb.append(map.get(ori[i])).append(" ");
		
		System.out.println(sb.toString());
	}
}

 

 

Rank

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

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());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] ori = new int[n];//원본배열
		int[] sub = new int[n];//오름차순 정렬할 배열
		for(int i=0; i<n; i++) {
			ori[i] = Integer.parseInt(st.nextToken());
			sub[i] = ori[i];
		}
		
		Arrays.sort(sub);//정렬
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int rank = 0;
		//key:요소값 , value:요소값에 해당하는 rank
		for(int i=0; i<n; i++) 
			if(!map.containsKey(sub[i])) map.put(sub[i], rank++);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++) //rank를 차례대로 넣고 출력 
			sb.append(map.get(ori[i])).append(" ");
		
		System.out.println(sb.toString());
	}
}

---

마치며

두가지 방법으로 풀어본 문제다.

그리고 이전에는 모르고 사용했지만 이번 문제를 통해 rank라는 개념을 알게된 문제다.