BAEKJOON / 백준 - JAVA 1015번 수열 정렬

2024.07.03기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 입력된 수열의 비내림차순을 했을 때에 그 숫자가 b배열에 몇번 인덱스인지를 출력하는 문제입니다.

조건에 사전순으로 가장 빠른 수열을 출력을 해야되기 때문에 중복된 수가 있다면 앞에서 부터 인덱스를 체크를 해줘야 합니다.

 

첫번째 예시로 예를 들어

로 들어왔다면

A의 배열은 이렇게 됩니다.

A	인덱스	0	1	2
	수열	2	3	1

 

정답을 보시면 P[]입니다.

P	인덱스	0	1	2
	수열	1	2	0

 

문제의 공식에서 B[P[i]] = A[i]이라고 나와 있습니다, 이걸 공식에 대입해보면,

i : 0  →   b[p[0]] = a[0]   →   b[1] = a[0]  →   b[1] = 2
i : 1  →  b[p[1]] = a[1]  →  b[2] = a[1]  →  b[2] = 3
i : 2  →  b[p[2]] = a[2]  →  b[0] = a[2]  →  b[0] = 1

 

이렇게 계산이 됩니다. 그러면 결국 B는

B	인덱스	0	1	2
	수열	1	2	3

B가 정확히 비내림차순으로 정렬이 되게 됩니다.

 

쉽게 말하면 B가 비내림차순으로 나올때에 인덱스를 출력하면 되는 문제입니다.

 

1. P배열과 A를 저장하는 배열을 생성했습니다.

int[] P = new int[n];
int[] arr = new int[n];

 

2. 정렬과 중복제거를 하여 참조할 변수를 구하기 위해 treeset을 활용했습니다.

// 정렬과 중복제거를 한번에 하기 위한 treeset
TreeSet<Integer> set = new TreeSet<>();

 

3. 그렇게 저장된 데이터를 이용해 set에 들어간 값을 하나씩 거내면 값을 올리는 방식으로 P배열에 저장을 해주었습니다.

// P배열에 들어갈 숫자와 set을 참조하는 숫자 변수
int index = 0, num;
while (!set.isEmpty()) {
    num = set.pollFirst();

    for (int i = 0; i < n; i++) {
        if (arr[i] == num) {
            P[i] = index;
            index++;
        }
    }
}

 

 

코드

package Main;

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));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 배열의 크기
		StringTokenizer st = new StringTokenizer(br.readLine()); // 수열
		
		// P배열을 저장할 배열
		int[] P = new int[n];
		
		// 수열을 저장하기 위한 배열
		int[] arr = new int[n];
		
		// 정렬과 중복제거를 한번에 하기 위한 treeset
		TreeSet<Integer> set = new TreeSet<>();
		
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			set.add(arr[i]);
		}
		
		// P배열에 들어갈 순자와 set을 참조하는 순자 변수
		int index = 0, num;
		while (!set.isEmpty()) {
			num = set.pollFirst();
			
			for (int i = 0; i < n; i++) {
				if (arr[i] == num) {
					P[i] = index;
					index++;
				}
			}
		}
		
		for (int p : P) {
			sb.append(p + " ");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}