[Java] 백준 18870.좌표 압축

➡️문제 링크

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

 

💡아이디어

솔직히 처음에는 좌표 압축..? 뭔 말이야 싶었다

문제를 다시 읽어보니 말만 좌표 압축!!! 이렇지

실상은 현재 주어진 배열의 각 원소마다 자신보다 작은 값 들이 몇 개 있는지(단, 중복X) 구하는 문제였다.

그래서 그대로 바로 구현!

 

 

✏️문제 풀이

1. Set, HashMap, 정렬 - 성공

처음에는 "서로다른"이라는 조건을 체크하지 못해서 바로 정렬+리스트+map으로 풀었다가 두 번제 테스트케이스를 돌리니 답이 틀렸다.

"서로 다른"을 어떻게 구현하면 좋을지 고민하다 그냥 Set 쓰기로 하고 다시 구현했다.

성공은 했지만 생각보다 시간이 올래 걸려서 다른 사람들은 어떻게 푸나 확인했더니 다른 방법으로 접근한 사람들이 많아서 다시 풀어 봤다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] nums = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		Set<Integer> set = new HashSet<>();
		for(int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
			set.add(nums[i]);
		}
		
		List<Integer> list = new ArrayList<>(set);
		Collections.sort(list);		// 오름차순 정렬
		HashMap<Integer, Integer> hmap = new HashMap<>();
		for(int i = 0; i < list.size(); i++) {
			if(hmap.containsKey(list.get(i))) continue;
			else hmap.put(list.get(i), i);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			sb.append(hmap.get(nums[i]) + " ");
		}
		
		// 출력
		System.out.println(sb);
	}

}

 

 

2. 배열, 이분 탐색 - 성공

나는 중복을 피하기 위해 Set을 썻고, 각 배열의 좌표압축 결과를 가져오기 위해 key-value의 HashMap을 썼다. 근데 이렇게 풀지 않고, 중복을 피하기 위해 배열을, 좌표 압축 결과는 이분탐색을 통해 구현한 풀이를 봤다.

내가 생각하지 못한 방법이라서 너무 신기했다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] nums = new int[N];
		int [] tmp = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
			tmp[i] = nums[i];
		}
		
		
		// 오름차순 정렬
		Arrays.sort(tmp);
		int maxNum = tmp[0];
		int count = 1;			// 중복 제거한 길이 
		for(int i = 1; i < N; i++) {
			if(tmp[i] > maxNum) {
				maxNum = tmp[i];	// 배열 속 최댓값 갱신
				count++;
			}
		}
		
		int [] result = new int[count];		// 중복 제거한 길이만큼 생성 -> 찐 중복제거한만큼 배열 만들기
		result[0] = tmp[0];
		maxNum = tmp[0];
		count = 1;
		for(int i = 1; i < N; i++) {
			if(tmp[i] > maxNum) {
				result[count++] = tmp[i];	// 중복제거한 값들을 저장
				maxNum = tmp[i];
			}
		}
		
		// 기존 배열에서 좌표 압축 실행 -> 이분 탐색 통해 값 탐색
		int left = 0;
		int right = count-1;
		int index = 0;
		StringBuilder sb = new StringBuilder();
		while(index < N) {
			int mid = (left+right)/2;
			
			if(result[mid] < nums[index]) left = mid+1;
			else if(result[mid] > nums[index]) right = mid-1;
			else {
				left = 0;				// 포인터 초기화
				right = count-1;
				sb.append(mid+" ");
				index++;
			}
		}

		// 출력
		System.out.println(sb);
	}

}

 

 

 

3. custom 클래스 정렬 - 성공

새로웠던 또 하나의 풀이!

list에 저장할 때 클래스형태로 저장을 하고 정렬을 한다.

이때 클래스는 {idx, value} 형태로 입력받을 때의 index와 값을 저장한다.

이후, value를 기준으로 오름차순 정렬하고 이 list를 기준으로 for문을 돌려 각 value마다 좌표압축 값을 저장한다.

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

public class Main {
	static class Point implements Comparable<Point>{
		int idx;
		int value;
		
		public Point(int idx, int value) {
			this.idx = idx;
			this.value = value;
		}
		
		public int compareTo(Point p) {
			return Integer.compare(this.value, p.value);
		}
		
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		List<Point> list = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			list.add(new Point(i, Integer.parseInt(st.nextToken())));
		}
		
		// 오름차순 정렬
		Collections.sort(list);
		int [] result = new int[N];		// 정답 저장할 배열
		int index = 0;
		for(int i = 0; i < N; i++) {
			Point p = list.get(i);
			if(i > 0 && p.value == list.get(i-1).value) {
				result[p.idx] = index - 1;
			}else {
				result[p.idx] = index++;
			}
		}
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			sb.append(result[i]+" ");
		}

		// 출력
		System.out.println(sb);
	}

}