백준 18870: 좌표 압축(java)

문제

---

풀이

 

입력 순서 그대로 정렬하지 않은 배열과 오름차순으로 정렬한 배열 2개를 사용했는데, arr가 sortedArr보다 작아질 때까지 추가로 탐색하는 과정을 거치기 때문에 시간 초과로 표시된다. (접은글 참고)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] arr=new int[N];	//원래 순서 그대로 저장할 배열
		int[] sortedArr=new int[N];	//오름차순으로 정렬할 배열
		
		for(int i=0; i<N; i++) {
			int n=Integer.parseInt(st.nextToken());
			arr[i]=n;
			sortedArr[i]=n;
		}
		
		Arrays.sort(sortedArr);
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(arr[i]<=sortedArr[j]) {
					sb.append(j).append(" ");
					break;
				}
			}
		}//이 과정에서 시간이 걸리는 듯
		
		System.out.println(sb);
	}
}

따라서 별도의 비교 과정 없이 숫자와 인덱스를 바로 대응시킬 수 있는 방법이 필요하므로, HashMap을 사용한다.

 

정렬하지 않은 배열(arr)과 정렬한 배열(sortedArr)을 모두 사용하는 것은 동일하나, 해시맵에 키와 인덱스를 저장할 때는 sortedArr만을 사용하고, arr는 입력 순서대로 출력할 때만 사용한다.

HashMap<Integer, Integer> hm=new HashMap<>();
		
int count=0;
for(int i=0; i<N; i++) {
	if(!hm.containsKey(sortedArr[i])) {
		hm.put(sortedArr[i], count);
		count++;
	}
}

오름차순 정렬된 순서대로 삽입하게 되므로, 반복문 마지막에 count를 1씩 증가시키면 증가하는 순서에 따라 인덱스가 배정된다.

for(int i=0; i<N; i++) {
	sb.append(hm.get(arr[i])+" ");
}

이후 arr을 이용해 입력된 순서대로 인덱스를 출력한다.

 

전체 코드

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[] arr=new int[N];
		int[] sortedArr=new int[N];
		
		for(int i=0; i<N; i++) {
			int n=Integer.parseInt(st.nextToken());
			arr[i]=sortedArr[i]=n;
		}
		
		Arrays.sort(sortedArr);
		
		HashMap<Integer, Integer> hm=new HashMap<>();
		
		int count=0;
		for(int i=0; i<N; i++) {
			if(!hm.containsKey(sortedArr[i])) {
				hm.put(sortedArr[i], count);
				count++;
			}
		}
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<N; i++) {
			sb.append(hm.get(arr[i])+" ");
		}
		
		System.out.println(sb);
	}
}