백준 18870 자바

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

18870번: 좌표 압축

 

접근 방식

못풀었다. 나보다 값이 작다면 +1을 하고 중복값을 제거하는 아이디어는 떠올렸다. 중복값 제거하니 Set이 떠올랐고 순위를 저장해서 조회하려면 Map이 필요해서 Set안에 Map을 사용해야하나?? 이런 생각만 든 채로 답을 봤다.

 

잘한 부분

순위를 매기고 중복을 제거하고 map을 찾은 부분은 잘 접근했다.

 

부족한 부분

확신이 부족했다. Set안에 Map을 넣으면 키값이 중복제거되고 거기서 2중for문을 다시 돌려야하나?? 이런 생각만 든 채로 실행해보지 않았다. 실행했어도 시간초과가 낫겠지만 아이디어가 떠올랐음에도 코드를 수행시키지 않은 것은 잘못된 부분이다.

 

그리고 StringBuilder를 사용하지 않으면 시간초과가 난다.

 

package backjon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		int[] result = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int s = Integer.parseInt(st.nextToken());
			arr[i] = result[i] = s;
			
		}
		Arrays.sort(arr);
		
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		int index = 0;
		for (int i = 0; i < N; i++) {
			if(!map.containsKey(arr[i])) map.put(arr[i], index++);
		}
		
		for (int i = 0; i < N; i++) {
			sb.append(map.get(result[i]) + " ");
		}
		
		System.out.println(sb);
		
	}
	
}