백준 - 2750번 - 수 정렬하기

이상훈·2023년 4월 11일
0

2750번

#1 선택정렬

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		int[] arr = new int[num];
		for (int i = 0; i<num; i++) {
			arr[i] = Integer.parseInt(bf.readLine());

		}
		int temp = 0; // 1. 선택정렬 시간복잡도 n 제곱
		for (int i = 0; i<num - 1; i++) {
			for (int j = i+1; j< num; j++) {
				if (arr[i] > arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}

		for (int N : arr) {
			System.out.println(N);
		}
	}

}

#2 Arrays.sort(arr);

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		int[] arr = new int[num];
		for (int i = 0; i<num; i++) {
			arr[i] = Integer.parseInt(bf.readLine());

		}
		Arrays.sort(arr); //2. O(nlogn) 최악은 n 제곱

		for (int N : arr) {
			System.out.println(N);
		}
	}

}

#3 Counting Sort

  • 통과하지는 못함. 양의 정수에서만 성공하게 로직을 짰다.
import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		int[] arr = new int[num];
		int max = 0;
		for (int i = 0; i<num; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		int[] counting = new int[max+1];
		int[] result = new int[num];

		// counting 배열 만들어주기
		for (int i = 0; i<num; i++) {
			counting[arr[i]]++;
		}

		// 누적합으로 counting 배열 채워주기
		for (int i = 1; i<max+1; i++) {
			counting[i] += counting[i-1];
		}

		// result 배열 채워주기
		for (int i = num-1; i>=0; i--) {
			counting[arr[i]]--;
			result[counting[arr[i]]] = arr[i];
		}

		for (int N : result) {
			if (N != 0) {
				System.out.println(N);
			}
		}
	}

}

풀이


오름차순으로 정렬하는데에는 여러가지 방법이 있다. 그 도중에 시간복잡도와 상황을 고려해서 가장 유리한 방법으로 풀어야 한다.

이번 문제에서는 매번 배열을 모두 돌며 max값을 도출하는 선택정렬과 자바 Array에서 지원하는 Arrays.sort(arr); 방법으로 풀었고 성능은 아래와 같다.


아래 = 선택정렬
위 = Arrays.sort(arr);

0개의 댓글