백준 18870번: 좌표 압축 [정렬][좌표압축] - Java

 

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

18870번: 좌표 압축

좌표 압축 알고리즘이 뭔지 몰라서 시간이 걸렸던 문제.

좌표 압축이란?

"입력 값의 범위에 비해 입력 갯수가 현저히 작을때, 배열의 값에 새로운 인덱스를 부여하는 기술"이다.

현재 입력받은 배열들을 오름차순으로 정렬 한다음, idx를 새로 부여한다. 그러면 값의 범위가 일정해진다.

위는 백준 18870 테스트케이스 1번을 예시로 idx 변환한 예시이다.

 

1. 입력좌표 오름차순 정렬

2. 입력좌표 새로운 idx 매핑

3. 좌표압축 시켜서 출력

 

<첫번째 시도: 시간 초과>

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream ("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		

		int N = Integer.parseInt(st.nextToken());
		int[] xArr = new int[N]; //원본좌표
		ArrayList<Integer> mapping = new ArrayList<Integer>(); //새 idx 매핑List
		
		//1. 원본좌표 입력
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			xArr[i] = num;
			
			//2. list에 새로운 idx체계 부여 
			if(!mapping.contains(num))
				mapping.add(num);
		}
		
		
		
		//2. 매핑list 정렬 (오름차순)
		Collections.sort(mapping);
		
        //3. 좌표압축
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < N; i++) {	
			bw.write(mapping.indexOf(xArr[i])+" "); 
		}
		bw.write("\n");
		bw.flush();
	}

}

위의 알고리즘은 O(N^2)이다. indexOf를 하기때문에 원본좌표와 매핑list를 N*N 반복한다.

시간제한이 2초이기 때문에 2억번의 연산만 수행이 가능한데,

• 1 ≤ N ≤ 1,000,000

조건 때문에, 최악의 경우인 N이 100만개에 중복이 없다면, 1,000,000 * 1,000,000 = 1,000,000,000,000번의 연산이 된다.

1조의 연산^^?ㅋ..

 

아무튼 그래서 HashMap에 모든 숫자의 Idx를 저장해놓고 바로 불러올수있도록 하는 방법을 택했다.

 

728x90

 

<두번째 시도: 성공>

import java.io.*;
import java.util.HashMap;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream ("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		

		int N = Integer.parseInt(st.nextToken());
		int[] xArr = new int[N]; //원본좌표
		TreeSet<Integer> set = new TreeSet<Integer>(); //새 idx 매핑List
		
		//1. 원본좌표 입력
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			xArr[i] = num;
			
			//2. set에 add 
			set.add(num); //set은 오름차순대로 자동정렬됨, 중복불가
		}
		
		
		
		
		//2. 새idx mapping 테이블만들기 
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		int idx = 0;
		for (int num : set) {
			map.put(num, idx++);
		}
		
		
		//3. 좌표압축
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < N; i++) {	
			bw.write(map.get(xArr[i])+" "); 
		}
		bw.write("\n");
		bw.flush();
		
	}

}

TreeSet은 중복을 허용하지 않고, 입력순서가 아닌 자체적인 순서로 정렬이 된다는 점을 이용했다.

그리하여 자동 오름차순으로 정렬되었을거니.. 앞에서부터 idx 0, 1, 2,... 를 부여하여 map에 숫자와 idx를 매핑하였다.

끝 ...!

 

728x90