[BOJ/백준 - 18870] 좌표 압축

문제 출처: https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

	public class BOJ_18870 {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	HashMap<Integer, Integer> hm = new HashMap<>(); //
	int size = Integer.parseInt(br.readLine());
	int[] arr = new int[size];
	int[] target = new int[size];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i=0; i<size; i++){
	int v = Integer.parseInt(st.nextToken());;
	arr[i] = v;
	target[i] = v;
	}
	Arrays.sort(arr);
	int dupCnt = 0;
	int before = 0;
	for(int i=0; i<arr.length; i++){
	if(i!=0 && before == arr[i]){
	dupCnt++;
	}
	before = arr[i];
	hm.put(arr[i], i-dupCnt);
	}
	for(int i=0; i<size; i++){
	sb.append(hm.get(target[i])).append(" ");
	}
	System.out.print(sb);
	}
	}

view raw BOJ_18870.java hosted with ❤ by GitHub

---

난 일단 문제 이해가 아예 안되서 문제가 뭘 뜻하는지만 찾아보고 풀어보았다

나처럼 문제의 뜻을 몰랐다면 설명을 듣고 다시 풀어보자

 

각각의 입력받은 좌표값을 X라고 했을때 X보다 앞에있는 좌표가 몇 개 있냐?

                                                             (값이 작은 좌표가 몇 개 있냐?)

이런 문제였다.

최대한 간단하게 쓴다고 했는데 잘 이해가 안된다면 미안하고 다른사람 설명을 찾아보셔야겠다

(백준 지문도 이해 못할만큼 국어 못함 당연히 설명도 좀 부족할 수도 있음)

 

1. 좌표라고 했으니 중복값을 지워야 하므로 입력값을 받으면서 해시맵에 해당 값을 넣어줌

2. 정렬

3. 내 앞의 원소의 갯수를 셈

4. 내 앞의 수와 같은지를 검사하고 같으면 중복을 체크하는 변수를 1 올려줌

5. 원소의 갯수 - 중복된 값을 하면 내 앞의 좌표 갯수가 나옴

 

예시로 된 데이터로 함 봐보자

 

일단은 이런식으로 그림을 그려보고 코드를 작성했고

최종적으로 계산할때마다 해시맵의 값을 갱신하는게 맘에 안들긴 했지만 일단 풀긴 푸럿당