18870번 좌표 압축

이왜틀?

---

18870번 좌표 압축 - 백준

4년 전의 기록이다.
화려한 시간초과의 향연!

import java.util.*;
import java.io.*;
			
public class Main{
    public static void main(String[] args){
		try{
				BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

				int n=Integer.parseInt(br.readLine());
				StringTokenizer st=new StringTokenizer(br.readLine()," ");

				int[] arr=new int[n];
				int[] result=new int[n];

				int idx=0;
				while(st.hasMoreTokens()){
					arr[idx++]=Integer.parseInt(st.nextToken());
				}

				for(int i=0;i<n;i++){
					for(int j=0;j<n;j++){
						if(i!=j&&arr[i]>arr[j]){
							result[i]++;
						}
					}
				}

				for(int i:result) bw.write(i+" ");
				bw.flush();

			}catch(Exception e){e.printStackTrace();}
	}
}

전체 순회하며 결과 배열에 숫자를 하나씩 더해간다.
좀 더 시간을 줄일 수 있게 접근해야한다.

설계

---

중복되는 요소가 있으니 Set을 활용해 중복을 거르고 정렬한다.
TreeSet을 쓰면 되겠다.
그 후 순서 인덱스를 매핑해서 원래 배열과 비교해 인덱스를 뽑아주면 된다.

구현

---

트리셋은 자동 정렬이 되니 손댈 필요가 없다.
맵에 인덱스를 value로 저장 후 원래 배열을 순회하며 맵에서 꺼내다 출력한다.

// 처음 입력받을 배열
int[] arr = new int[n];
// 중복제거 및 정렬용 트리셋
Set<Integer> set = new TreeSet<>();
// 압축 매핑용 맵
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0 ; i < n ; i++) {
	int token = Integer.parseInt(st.nextToken());
	arr[i] = token;
	set.add(token);
}

// 맵에 매핑
Iterator<Integer> iter = set.iterator();
int idx = 0;
while (iter.hasNext()) {
	map.put(iter.next(), idx++);
}

// 출력
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < n ; i++) {
	sb.append(map.get(arr[i])).append(" ");
}

채점

---

반성

---

이상하다 4년전이면 컬렉션 쓰는 법 정도는 알았을 텐데…

코드 확인

---

Link to GitHub