본문 바로가기
백준

백준 18870: 좌표 압축(java)

by unhyepnhj 2024. 9. 3.

문제


풀이

 

입력 순서 그대로 정렬하지 않은 배열과 오름차순으로 정렬한 배열 2개를 사용했는데, arr가 sortedArr보다 작아질 때까지 추가로 탐색하는 과정을 거치기 때문에 시간 초과로 표시된다. (접은글 참고)

더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int[] arr=new int[N];	//원래 순서 그대로 저장할 배열
		int[] sortedArr=new int[N];	//오름차순으로 정렬할 배열
		
		for(int i=0; i<N; i++) {
			int n=Integer.parseInt(st.nextToken());
			arr[i]=n;
			sortedArr[i]=n;
		}
		
		Arrays.sort(sortedArr);
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(arr[i]<=sortedArr[j]) {
					sb.append(j).append(" ");
					break;
				}
			}
		}//이 과정에서 시간이 걸리는 듯
		
		System.out.println(sb);
	}
}

따라서 별도의 비교 과정 없이 숫자와 인덱스를 바로 대응시킬 수 있는 방법이 필요하므로, HashMap을 사용한다.

 

정렬하지 않은 배열(arr)과 정렬한 배열(sortedArr)을 모두 사용하는 것은 동일하나, 해시맵에 키와 인덱스를 저장할 때는 sortedArr만을 사용하고, arr는 입력 순서대로 출력할 때만 사용한다.

HashMap<Integer, Integer> hm=new HashMap<>();
		
int count=0;
for(int i=0; i<N; i++) {
	if(!hm.containsKey(sortedArr[i])) {
		hm.put(sortedArr[i], count);
		count++;
	}
}

오름차순 정렬된 순서대로 삽입하게 되므로, 반복문 마지막에 count를 1씩 증가시키면 증가하는 순서에 따라 인덱스가 배정된다.

for(int i=0; i<N; i++) {
	sb.append(hm.get(arr[i])+" ");
}

이후 arr을 이용해 입력된 순서대로 인덱스를 출력한다.

 

전체 코드

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 br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int[] arr=new int[N];
		int[] sortedArr=new int[N];
		
		for(int i=0; i<N; i++) {
			int n=Integer.parseInt(st.nextToken());
			arr[i]=sortedArr[i]=n;
		}
		
		Arrays.sort(sortedArr);
		
		HashMap<Integer, Integer> hm=new HashMap<>();
		
		int count=0;
		for(int i=0; i<N; i++) {
			if(!hm.containsKey(sortedArr[i])) {
				hm.put(sortedArr[i], count);
				count++;
			}
		}
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<N; i++) {
			sb.append(hm.get(arr[i])+" ");
		}
		
		System.out.println(sb);
	}
}

'백준' 카테고리의 다른 글

백준 2003: 수들의 합(java)  (0) 2024.09.09
백준 9655: 돌 게임(java)  (0) 2024.09.05
11659: 구간 합 구하기 4(java)  (0) 2024.09.02
백준 3477: 버그왕(java)  (0) 2024.08.31
백준 10816: 숫자 2(java)  (0) 2024.08.28