반응형
백준 18870번 문제 - 좌표 압축
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에
www.acmicpc.net
문제 분석
- 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
- Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
- 가장 작은 수를 0으로 해서 정렬에 따라 숫자가 1씩 증가한다.
- 중복 수는 동일한 수를 준다.
- ex) 2 4 -10 4 -9 → -10 -9 2 4 4 → -10:0 -9:1 2:2 4:3 4:3
해결 포인트
- 정렬하지 않는 배열, 정렬하는 배열 두가지 구현
- 정렬하는 배열 사용법
- 첫번째, TreeSet으로 중복 처리 및 정렬한 후, List로 변환해서 indexOf로 해당 숫자 정렬 결과 알아내기 (인덱스 = 압축 결과)
- 실패 (List 변환에서 컴파일 에러 : Java 11에서는 toList() 메서드가 List 인터페이스에서 직접 제공되지 않는다.) - 두번째, ArrayList를 Collections.sort 한 후, indexOf로 해당 숫자 정렬 결과 알아내기
- 실패 (indexOf 가 생각보다 시간이 오래 소요, 시간 초과) - 세번째, ArrayList 중복 제거는 stream().distinct().toArray()로 해결. 이진탐색으로 해당 숫자 정렬 결과 알아내기
- 성공 !
- 첫번째, TreeSet으로 중복 처리 및 정렬한 후, List로 변환해서 indexOf로 해당 숫자 정렬 결과 알아내기 (인덱스 = 압축 결과)
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int [] nums = new int[N];
int [] sort = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
nums[i] = Integer.parseInt(st.nextToken());
sort[i] = nums[i];
}
sort = Arrays.stream(sort).distinct().toArray();
Arrays.sort(sort);
for (int i = 0; i < N; i++) {
bw.write(binary(sort, nums[i], 0, sort.length) + " ");
}
bw.flush();
bw.close();
}
public static int binary(int [] sort, int value, int start, int end) {
int index = (start + end)/2;
if(sort[index] == value) return index;
if(sort[index] > value)
return binary(sort, value, start, index-1);
return binary(sort, value, index+1, end);
}
}
반응형
'CodingTEST' 카테고리의 다른 글
[백준 14940] 쉬운 최단거리 (JAVA) (0) | 2023.12.13 |
---|---|
[프로그래머스] 베스트앨범 (JAVA) (0) | 2023.12.10 |
[백준 2630] 색종이 만들기 (JAVA) (0) | 2023.12.08 |
[백준 1927] 최소 힙 (JAVA) (0) | 2023.12.08 |
[백준 1012] 유기농 배추 (JAVA) (1) | 2023.12.08 |