문제
P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
입력
첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.
예제 입력 1
3
2 3 1
예제 출력 1
1 2 0
예제 입력 2
4
2 1 3 1
예제 출력 2
2 0 3 1
예제 입력 3
8
4 1 6 1 3 6 1 4
예제 출력 3
4 0 6 1 3 7 2 5
사실 문제 푸는 것 보다 문제 자체가 이해가 잘 안 돼서 처음에 질문 게시판 들여다보고 예제 보면서 어떻게 풀면 될지 유추했다.
나는 0~N-1의 숫자를 이용해 A 배열에 나온 숫자의 크기에 따른 순서는 유지하되, 같은 숫자의 경우에 해당 위치에 들어가는 숫자들이 오름차순이 되도록 출력하면 된다고 이해했다.
우선 원본 배열 A, 오름차순 정렬용 배열 A2 이렇게 2개의 배열을 생성했다.
이제 A 배열의 숫자의 크기에 따른 순서는 유지되면서, 0부터 오름차순으로 숫자가 할당되게 해야한다.
여기서 A에 중복된 숫자가 있을 수 있으니, map을 이용해 A 배열에 있는 숫자(key)에 할당될 P의 숫자를 큐 형태로 저장(value)하도록 했다.
오름차순 순서대로 숫자가 저장하되 사용한 숫자를 쉽게 제거하기 위해 큐를 사용했다.
반복문을 통해 정렬된 A2 배열을 돌면서 각각의 숫자에 <- 순서대로 숫자(i가 0부터 N-1까지 순서대로 숫자가 됨)를 할당해줬다.
마지막으로 원래의 A 배열을 돌면서 각각의 숫자에 할당된 숫자를 큐에서 하나씩 꺼내 출력해주면 된다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] A = new int[N], A2 = new int[N]; // A는 원본, A2는 정렬하기 위한 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = A2[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A2); // A2 배열 오름차순 정렬
Map<Integer, Queue<Integer>> map = new HashMap<>(); // 각각의 숫자에 할당될 오름차순 숫자 큐에 넣어서 맵 형태로 저장
for (int i = 0; i < N; i++) {
Queue<Integer> que = map.getOrDefault(A2[i], new LinkedList<>());
que.add(i);
map.put(A2[i], que);
}
// 원본 A 배열 돌면서 각각의 숫자에 할당된 숫자 큐에서 꺼내서 출력
for (int i = 0; i < N; i++) {
bw.write(map.get(A[i]).poll()+" ");
}
bw.flush();
bw.close();
br.close();
}
}