[JAVA] 백준 18870번 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

 

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

 

풀이과정

1. value값과 index값을 가진 GET 노드를 정의한다.

( 처음 풀이과정에서 sort 두 번 하기위해서 만들었는데 그냥 그대로 이용 )

 

public static class GET{
		int val;
		int idx;
		public GET(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}
	}

 

2. ArrayList arr ( 입력으로 받은 value값을 순서대로 가지는 리스트 ) ,

val_idx ( 입력받은 value, 값과 입력받은 순서대로 index를 부여한 GET 노드를 가지는 리스트 ) 생성 및 입력받기

 

public static ArrayList<Integer> arr = new ArrayList<>();;
public static ArrayList<GET> val_idx = new ArrayList<>();

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr.add(num);
			val_idx.add(new GET(num, i));
		}

 

3. value값을 기준으로 오름차순 정렬

 

Collections.sort(val_idx, new Comparator<GET>() {
            @Override
            public int compare(GET s1, GET s2) {
                if (s1.val < s2.val) {
                    return -1;
                } else if (s1.val > s2.val) {
                    return 1;
                }
                return 0;
            }
        });

 

4. val_idx 리스트를 처음부터 반복문을 이용해서 중복된 값 제거하기

 

for(int i=0; i<val_idx.size(); i++) {
			if(i == 0) {
				keep = val_idx.get(i).val;
			}
			else {
				if(keep == val_idx.get(i).val) {
					val_idx.remove(i);
					i--;
				}
				else {
					keep = val_idx.get(i).val;
				}
			}
		}

 

5. BinarySearch 구현

 

public static int BinarySearch(int pos) {
		int left = 0;
		int right = val_idx.size() - 1;

		while(left < right){
			int mid = (left + right ) / 2;
			if(val_idx.get(mid).val >= pos)
				right = mid;
			else
				left = mid + 1;
		}
		return right;
	}

 

6. BinarySearch를 이용해서 답 구하기

 

for(int i=0; i<arr.size(); i++){
			int result = BinarySearch(arr.get(i));
			sb.append(result + " ");
		}
		
System.out.println(sb);

 

+. 배열에 result값들을 입력받아 반복문을 통해서 답을 출력하니 시간초과

++. 그래서 StringBuilder 사용해서 했는데도 시간초과 -> 이유를 모르겠음

 

 

Solution ( 시간초과 )

import java.util.*;

import java.io.*;

public class BaekJoon_18870_좌표압축 {
	
	public static class GET{
		int val;
		int idx;
		public GET(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}
	}
	
	public static int N, keep;
	public static ArrayList<Integer> arr = new ArrayList<>();;
	public static ArrayList<GET> val_idx = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr.add(num);
			val_idx.add(new GET(num, i));
		}
		
		Collections.sort(val_idx, new Comparator<GET>() {
            @Override
            public int compare(GET s1, GET s2) {
                if (s1.val < s2.val) {
                    return -1;
                } else if (s1.val > s2.val) {
                    return 1;
                }
                return 0;
            }
        });
		
		for(int i=0; i<val_idx.size(); i++) {
			if(i == 0) {
				keep = val_idx.get(i).val;
			}
			else {
				if(keep == val_idx.get(i).val) {
					val_idx.remove(i);
					i--;
				}
				else {
					keep = val_idx.get(i).val;
				}
			}
		}
		
		for(int i=0; i<arr.size(); i++){
			int result = BinarySearch(arr.get(i));
			sb.append(result + " ");
		}
		
		System.out.println(sb);
		br.close();

	}
	
	public static int BinarySearch(int pos) {
		int left = 0;
		int right = val_idx.size() - 1;

		while(left < right){
			int mid = (left + right ) / 2;
			if(val_idx.get(mid).val >= pos)
				right = mid;
			else
				left = mid + 1;
		}
		return right;
	}

}