백준 18870 <좌표 압축>

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

주어진 정수들의 Ranking을 매기는 문제이다. 적절한 자료구조를 활용해야겠다는 생각을 처음에 못하고 일단 정렬된 배열과 원본 배열을 만들어놓고, 이진탐색을 해보자.라는 생각을 했다. (시간제한이 빡세서)

 

일단 첫번째 정렬된 배열을 만들자.  > 이건 좋은 아이디어. 애사당초에 ranking을 할때 정렬된 배열 하나는 꼭 있어야한다. 시간제한이 있으니 nlogn짜리 arrays.sort()를 사용했다. 여기서 문제는

정렬된 배열은 원본 배열의 인덱스를 바꿔놓는다. 즉 원본과는 다르기에 출력해야하는 순서를 어긴다.

 

난 여기서 이 순서를 때문에 정렬된 배열을 돌며 이진탐색을 돌며 인덱스를 return 했는데 문제가 2개 발생한다.

1. 시간 초과

2. 원본 배열에 중복된 값이 있을 경우 - 예를들어 -1 2 -3 -3 4 라 치면

최솟값인 -3의 답은 0 이겠다 (0번째 인덱스니까) 근데 -1은 현재 2번째 인덱스에 위치했으니 2가 출력이 된다.

하지만 자신보다 작은 값은 최솟값인 -3. 즉 1이 출력이 되어야한다.

 

만약, 원본 배열이 중복되지 않은 것이 없다고 보장된다면 풀이 방식이 적절하지만 그렇지 않으니,,

 

 

즉 중복된 값의 랭킹은 동일하게 넣어야하며, 그렇지 않은 새로운 값에 그 다음 랭크를 매겨야하니 방법은 

1. set

2. map

 

여기서 map을 쓰면 순서가 없다하더라도, get()을 이용하여 추적할수있으니 값을. 이를 이용해 중복되지 않은 값일때 ranking을 매기고 넣었다면 다음값의 랭크를 매겨 rank++;를 한다. 이때는 당연히 sortedarray를 한바퀴 쭉 돌겠다. 

그렇다면 자연스레 랭킹이 딱딱 맞춰지니.

package 백준;
import java.util.*;
import java.io.*;

public class _18870_좌표압축 {
	
	

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer,Integer> mp = new HashMap<>(); 
		int n = Integer.parseInt(br.readLine());
		int originarr[] = new int[n];
		
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++) {
			originarr[i] = Integer.parseInt(st.nextToken());
			
		}
		int sortedarr[] = originarr.clone();
		
		Arrays.sort(sortedarr);
		
		int rank = 0;
		for(int x :sortedarr) {
			
			if(!mp.containsKey(x)) {
				mp.put(x, rank);
				rank++;
			}
			
			
		}
		
		StringBuilder sb = new StringBuilder();
		for(int x : originarr) {
			sb.append(mp.get(x)).append(" ");
		}
		
		System.out.println(sb);
		
		
		  

	}

}