[Baekjoon] 1015_수열 정렬

Silver IV

문제(출처: https://www.acmicpc.net/problem/1015)

---

< 수열 정렬 >

 

문제 풀이 

 

오름차순으로 만드는 수열 P를 구하기 위해서는 배열 A의 원소 중에서 작은 값부터 작은 값을 주면 된다.

 

문제 예제에서 주어진 것으로 설명해 보면

 

A [2,3,1]

P [1,2,0]

 

-> B [1]=2, B [2]=3, B [0]=1로 B [1,2,3]이 완성된다.

 

 my solution (Java)

import java.io.*;
import java.util.*;

public class _1015_ { // 수열 정렬

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0])
					return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < n; i++) {
			queue.add(new int[] { Integer.parseInt(st.nextToken()), i });
		}

		int[] result = new int[n];
		int idx = 0;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			result[temp[1]] = idx++;
		}

		for (int i = 0; i < n; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}
}

 

Main

변수)
n : 배열 A 크기
queue : [배열 A 값, index]를 저장하며 배열 A 값을 기준으로 오름차순 정렬, 배열 A 값이 같다면 index 기준으로 오름차순 정렬
result : 수열 P
idx : 수열 P 값 

 

- 배열 A 크기(n) 입력

- 배열 A의 원소를 입력받아 우선순위 큐에 저장

- 우선순위 큐가 빌 때까지 반복

: 원소를 뽑아 index 위치에 0부터 저장

- 수열 P 출력

---

---