[백준_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이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_18870 {
	/*
	 * <좌표 정렬>
	 * 입력 받은 좌표 값을 오름차순으로 정렬했을 때의 순서를 표시하는 것(단, 중복 값은 제외한다.)
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] arr=new int[n];
		int[] arrclone;
		int count=0;
		// 좌표 값과 인덱스를 저장 가능한 HashMap을 사용한다.
		Map<Integer, Integer> map=new HashMap<Integer, Integer>();
		StringBuilder sb=new StringBuilder();
		
		for(int i=0;i<n;i++)
			arr[i]=sc.nextInt();
		
		arrclone=arr.clone();
		
		Arrays.sort(arrclone); // 오름차순 정렬
		
		for(int i=0;i<arrclone.length;i++) {
			// 만약 map에 이미 존재하는 값이라면 무시하고 아니라면 좌표 값과 인덱스를 저장
			if(!map.containsKey(arrclone[i]))
				map.put(arrclone[i], count++);
		}
		
		// 배열에 저장된 좌표값에 알맞은 인덱스 출력
		for(int i=0;i<arr.length;i++)
			sb.append(map.get(arr[i])).append(" ");
		
		System.out.println(sb);
	}

}

 

[고찰]

 처음에는 2중 for문을 사용하여 각 좌표마다 다른 모든 좌표와 비교하여 해당 좌표 값 보다 작은 값을 만나면 count를 증가시키는 방식으로 해결했었다. 하지만 시간 초과가 생겨 다른 풀이법이 필요했다. 다른 사람들의 코드를 참고하니 HashMap을 사용하여 효율적으로 코드를 구성하였기에 나도 이번 문제를 통해 HashMap의 사용법을 익히는 시간을 가졌다. 아직 익숙해지기 위해서는 여러 문제를 풀어봐야 할 것 같다.