백준 18870 좌표 압축 (JAVA 자바 풀이)
📌 문제
수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.
💎 문제 분석
for문을 이중으로 반복해서 사용할시 N의 범위가 100만이므로 1초 + a가 되면서
시간 제한에 걸려버린다.
이 문제는 중복을 처리하는 과정에서 연산이 많이 든다. 따라서 일반적인 흐름에서 답을 구하기보다는
sort를 통해 정렬을 해주고 idx를 이용해서 푸는 아이디어가 필요하다.
hashmap을 이용한다.
💡 코드 구현
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 bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int numberOfCoordinates = Integer.parseInt(bufferedReader.readLine());
int[] coordinates = receiveCoordinates(bufferedReader, numberOfCoordinates);
int[] coordinatesCopied = coordinates.clone(); // 정렬을 수행하고 order를 구하기위한 copy 배열
Arrays.sort(coordinatesCopied);
HashMap<Integer, Integer> orderedNumbers = new HashMap<>();
int order = 0;
for (int i = 0; i < coordinatesCopied.length; i++) {
if (orderedNumbers.containsKey(coordinatesCopied[i])) {
continue;
}
orderedNumbers.put(coordinatesCopied[i], order);
order++;
}
StringBuilder stringBuilder = new StringBuilder();
for (int number : coordinates) {
stringBuilder.append(orderedNumbers.get(number)).append(" ");
}
System.out.println(stringBuilder);
}
private static int[] receiveCoordinates(BufferedReader bufferedReader, int numberOfCoordinates) throws IOException {
int[] coordinates = new int[numberOfCoordinates];
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < numberOfCoordinates; i++) {
coordinates[i] = Integer.parseInt(stringTokenizer.nextToken());
}
return coordinates;
}
}
입력 배열을 받을 때 2차원 배열을 통해 idx를 같이 받는 방식으로 구현하면 copy 없이 idx를 사용할 수 있다.
이때 앞의 값으로 정렬하면 뒤의 값은 따라온다.
int[][] xs = new int[N][2];
for (int i = 0; i<N; i++){
xs[i][0] = Integer.parseInt(bufferedReader.readLine());
xs[i][1] = i;
}
Arrays.sort(xs, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
return o1[0] - o2[0];
}
});
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 25501 재귀의 귀재 (JAVA 자바 풀이) 펠린드롬 (0) | 2022.12.03 |
---|---|
백준 10870 피보나치 수 5 (JAVA 자바 풀이) (0) | 2022.12.03 |
백준 10814 나이순 정렬 (JAVA 자바 풀이) (0) | 2022.12.02 |
백준 11651 좌표 정렬하기 2 (JAVA 자바 풀이) (0) | 2022.12.02 |
백준 11650 좌표 정렬하기 (Python 파이썬 풀이) (0) | 2022.12.02 |