[백준 18870] 좌표 압축 - Java

 

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

---

❓
처음 낸 답안은 시간초과가 나 통과되지 못했다.
그런데 어떻게 풀어서 시간을 줄여야 할지 감도 안 잡혀서 결국 다른 사람들의 풀이를 보고 뭐가 다른지 비교함.

❗
ArrayList 대신 int 배열을 사용해 충분히 풀 수 있는 문제였다.
좌표 순위를 ArrayList의 인덱스로 구분해 문제를 풀었는데(풀이 1), 이는 HashMap을 사용해 좌표의 순위를 좌표와 연결하여 해결 가능(풀이 2)

 

✨ 참고

https://st-lab.tistory.com/279

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

https://coding-factory.tistory.com/548

[Java] 자바 배열을 복사하는 다양한 방법 (깊은복사, 얕은복사)

---

 

풀이 1

• 시간초과

• 입력 받은 N개의 좌표를 저장할 ArrayList 생성
• 중복된 좌표를 제거하기 위해 ArrayList를 Set으로 변경
• Set을 다시 ArrayList로 변경 후 정렬
  • 이 때 정렬된 ArrayList는 처음 좌표 입력 된 ArrayList와 구분함
• 정렬되지 않은 ArrayList를 차례로 돌며, 정렬된 ArrayList에서 해당 값이 위치하는 인덱스 출력

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		// 입력받은 좌표
		ArrayList<Integer> points = new ArrayList<Integer>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<n; i++) {
			points.add(Integer.parseInt(st.nextToken()));
		}
		
		// 중복 좌표 제거
		Set<Integer> removePoints = new HashSet<Integer>(points);
		ArrayList<Integer> sortedPoints = new ArrayList<Integer>(removePoints);
		Collections.sort(sortedPoints);
		
		StringBuffer sb = new StringBuffer();
		for (int i=0; i<n; i++) {
			sb.append(sortedPoints.indexOf(points.get(i))).append(' ');
		}
		System.out.println(sb);
	}

}

 

---

 

풀이2

• 입력 받은 N개의 좌표를 저장할 int 배열 생성
• 그 좌표를 정렬할 int 배열 추가 생성 후 정렬
• 각 좌표(key)와 함께 그 좌표의 순위(value)를 함께 저장할 HashMap 생성
  • 좌표 순위 알려줄 rank 변수 선언
  • 위에서 정렬한 배열을 순서대로 돌며 [ic]rank + 1[/ic]
• 정렬되지 않은 배열을 순서대로 돌며 HashMap에서 해당 좌표의 순위 출력

📍 주의
입력 받은 좌표가 저장되어 있는 int 배열과 똑같은 값을 가지는 int 배열을 새로 생성할 때, [ic]int[] sortedPoints = points[/ic]와 같이 코드를 작성하면 얕은 복사가 되어 두 변수가 같은 배열을 가리키게 됨. (복사 의미 X)
반드시 배열을 새롭게 선언해 각 값을 차례로 복사해야 깊은 복사가 되어 두 배열이 값만 같은 다른 배열이 될 수 있음

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		// 입력 받은 N개의 좌표
		int[] points = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<n; i++) {
			points[i] = Integer.parseInt(st.nextToken());
		}
		
		// 입력 받은 좌표를 정렬할 새로운 배열
		int[] sortedPoints = new int[n];
		for (int i=0; i<n; i++) {
			sortedPoints[i] = points[i];
		}
		Arrays.sort(sortedPoints);
		
		/*
		 * <좌표, 좌표 순위>
		 * 정렬된 좌표 배열을 순서대로 돌면서 rank++
		 */
		HashMap<Integer, Integer> pointMap = new HashMap<Integer, Integer>();
		int rank = 0;
		for (int p : sortedPoints) {
			if (!pointMap.containsKey(p)) {
				pointMap.put(p, rank);
				rank++;
			}
		}
		
		
		StringBuffer sb = new StringBuffer();
		for (int i=0; i<n; i++) {
			sb.append(pointMap.get(points[i])).append(' ');
		}
		System.out.println(sb);
	}

}