문제
풀이
입력 순서 그대로 정렬하지 않은 배열과 오름차순으로 정렬한 배열 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 |