문제 url:
수 정렬하기
문제:
🤔 문제 알아보기
문제는 간단하다. N개만큼 입력 받은 후 해당 값을 오름차순으로 정렬하여 한 줄에 하나씩 출력하는 문제이다.
문제보다는 정렬을 하는 방법이 더 중요하니, 코드로 더 알아보도록 하자.
🐱👤 실제 코드
import java.io.*;
import java.util.Arrays;
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());
int[] arr = new int[N];
for(int i = 0; i< N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for(int i = 0; i< N; i++) {
System.out.println(arr[i]);
}
}
}
Arrays.sort() 메서드는 배열을 오름차순 할 때 사용하는 메서드로, 배열을 오름차순으로 정렬할 수 있다. 그 후, N만큼 반복하여 값을 불러오면 되는 간단한 코드이다.
그렇다면, Arrays.sort() 메서드는 무엇인지 알아보도록 하자,
👀 Arrays.sort()
Arrays.sort()는 java.util.Arrays 클래스에 존재하는 메서드로, Arrays는 정적 메서드로 인스턴스(객체)를 생성하지 않고 바로 사용할 수 있다.
sort()메서드에 static으로 정적 메서드 표시를 한 것을 볼 수 있다.Arrays.sort() 메서드에 대해서 간략히 설명하면 using papago
지정한 배열을 오름차순 숫자로 정렬합니다.
구현 참고: 정렬 알고리즘은 블라디미르 야로슬라프스키(Vladimir Yaroslavsky), 존 벤틀리(Jon Bentley), 조슈아 블로흐(Joshua Bloch)가 제작에 참여한 이중 피봇 퀵소트(Dual-Pivot Quicksort)입니다.
이 알고리즘은 다른 퀵소트의 성능이 2차 성능으로 저하되는 많은 데이터 세트에서 O(n log(n)) 성능을 제공하며, 일반적으로 기존 (원 피봇) 퀵소트 구현보다 빠릅니다.
매개 변수:
a – 정렬할 배열
즉 배열을 오름차순으로 정렬하고, (Dual-Pivor Quicksort)로, 다른 퀵소트보다 빠르다는 설명이다. 또한 시간 복잡도는 평균적으로 O(n log(n))를 제공한다고 한다.
※다른 블로그를 참고하니 아래와 같은 시간 복잡도를 가진다고 한다.
Best Cases : O(nlog(n))
Average Cases : O(nlog(n))
Worst Cases :O(n^2)
백준이나 프로그래머스가 각잡고 데이터를 나쁘게 주는 경우 O(N^2)으로 효율이 떨어질 수 있어도, 정렬로서 O(nlog(n)을 가지기에 나쁘지 않은 정렬이라고 한다.
sort의 로우 코드까지 확인한 후 글을 적어보고자 했으나,
아직 그걸 다 이해하기엔 실력이 부족하여 여기까지만 하겠다.여담으로, 내림차순을 할 때도 Arrays.sort() 메서드를 사용하는데, 이때는 뒤에 다른 파라미터 값도 넣어야 한다.
Arrays.sort(integer[]a , Collections.reverseOrder());
💢 내림차순시 주의
위의 코드처럼 Collections.reverseOrder() 메서드를 사용해 가능한데,
문제는 해당 메서드의 데이터 타입은 primitive type(원시타입) 이 아닌 reference type(참조 타입)을 사용하기 때문에
배열 타입을 int가 아닌 integer로 나타낸 후 sort()를 해줘야 한다는 것이다.
🤢 코드 리팩토링
여기까지 필자가 풀어본 방식과 그에 대한 풀이를 설명했다. 여기서 끝난다면! 해당 블로그의 identity가 없어진다.
이제는 Arrays.sort()와 같은 정적 메서드를 이용한 정렬이 아닌 타 블로그를 참조하며 다른 방법들을 연습해보고자 한다.
👍 선택 정렬(selection sort)
import java.io.*;
import java.util.Arrays;
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());
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for(int i = 0; i < arr.length-1; i++) {
for(int j = i+1; j < arr.length; j++ ) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
선택 정렬은, 첫 번쨰 인덱스와 뒤의 인덱스 값을 비교해서 작으면 앞으로 크면 뒤로 옮기는 작업을 통해 정렬을 하는 방법으로 시간 복잡도가 O(N^2)으로 sort(O(N log(N))에 비해서는 좋지 않다.
선택 정렬은 다시 정리해서 한번 올려보도록 하겠다.
✌ 계수 정렬(counting sort)
계수정렬은 정렬에서 무려 시간 복잡도가 O(N)에 해당하는 매우 빠른 알고리즘이다.
계수정렬에 대해서는 사실 아는 바가 없어 선택 정렬과 함께 따로 세션을 나눠 정리하여 올리고자 한다.
그래도 당장 알고 싶은 분을 위해 현재 공부중인 페이지를 공유하면 아래 링크를 확인
자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬) Stranger's LAB
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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());
// arr이 왜 2001??
// 문제에서 N은 1000이하의 값을 가지는데,
// 이 값은 절댓값이 1000보다 작거나 같은 수라고 한다.
// 그래서 2000을 입력한 것이며
// 나머지 1은 0의 자리를 의미 (즉, 0번째 인덱스는 결국 1000과 동일)
boolean[] arr = new boolean[2001];
for(int i = 0; i < N; i++) {
arr[Integer.parseInt(br.readLine()) + 1000] = true;
}
// -1000을 하면 0번째 인덱스부터 혹은, 음수부터 정렬되서 출력
for(int i = 0; i < 2001; i++) {
if(arr[i]) {
System.out.println(i - 1000);
}
}
}
}🤢 회고
이제 정렬 문제까지 왔는데.. 정렬에도 퀵, 선택, 계수, 버블 등 여러 정렬이 존재한다. 해당 정렬을 전부 마스터하려고 오래걸리겠지만 노력해서 빠르게 습득하고자 해야겠다.
