[백준/JAVA] 18870번: 좌표 압축

🔺 문제

18870번: 좌표 압축

 

🔺 코드

- 시간 초과 풀이

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
	    var br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    
	    var st = new StringTokenizer(br.readLine(), " ");	    
	    for(int i=0 ; i < n ; i++) {
	        arr[i] = Integer.parseInt(st.nextToken());
	    }
        
        int[] cnt = new int [n];
        for(int i=0 ; i < n ; i++) {
            for(int j=0 ; j < n ; j++) {
                if(i!=j && arr[i] > arr[j])
                    cnt[i]++;
            }
        }
        
        for(int i : cnt) {
            System.out.print(i + " ");
        }
	}
}

중복을 생각하지 못 해 답을 틀림ㅎ

 

 

- 정답

import java.util.*;
import java.io.*;

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

✅ 해결 아이디어
- 좌표 압축 : 각 원소의 순위를 매기는 문제
- Map 사용해 <좌표값, 좌표값의 최소 인덱스> 저장 (HashMap - 중복 제거)
- map에 이미 존재하는 좌표라면 무시. 아니라면 좌표값과 순위 저장

 

---

(참고)

✔ 풀이

[백준] 18870번 : 좌표 압축 - JAVA [자바]

 

[백준] 18870번: 좌표 압축 - JAVA

 

[백준알고리즘-JAVA]18870번 풀이(좌표 압축) - 초보도 이해하는 풀이