[데알] 백준 알고리즘 No. 2750 수 정렬하기(Java)

 

■ 문제 링크

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

■ 소스코드

 

1)   배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	// array 사용
	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<arr.length;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr, 0, arr.length);
		
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
	}

}

 

2)  ArrayList  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	//List 사용
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		List<Integer> arrayList = new ArrayList<>();
		
		for(int i=0;i<N;i++) {
			arrayList.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(arrayList);
		
		for(int num : arrayList) {
			System.out.println(num);
		}
		
	}

}

 

3)  LinkedList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {
	//LinkedList 사용
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		List<Integer> linkedList = new LinkedList<>();
		
		for(int i=0;i<N;i++) {
			linkedList.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(linkedList);
		
		for(int num : linkedList) {
			System.out.println(num);
		}
		
	}

}

  

 

■ 풀이

 

 배열은 Arrays클래스에 내장된 sort( ), ArrayList와 LinkedList는 Collentions클래스에 내장된 sort( )를 사용했다.

프로그래밍 언어들 중 기본적으로 지원되는 내장된 정렬 메서드 대부분 *퀵 정렬을 기본으로 둔다.  

(C도, java도, python도 모두 sort관련 함수를 가지고 있다.)

 코드의 큰 차이가 없다. 사용한 클래스가 다르지만 결국 sort( )라는 메서드 덕에 간단하게 풀 수 있었던 문제였다. 자료

구조만 변경해서 풀어보고 실행 시간 차이가 있다는 것도 확인했다. 

 

 

---

* 퀵 정렬이란?

잠깐 퀵 정렬에 대해 알아가자면..

1) 비어있는 배열이거나 원소가 하나인 경우( 기본단계라고도 부름 )

→ 정렬할 필요 없이 그대로 리턴한다.

2) 원소가 두 개인 경우

→ 두 원소를 비교하고 첫 번째가 두 번째 원소보다 크다면 자리를 교환하고 리턴한다.

3) 원소가 세 개 이상인 경우(여기서부터 핵심)

① 기준이 될 원소를 고른다.(기준 원소 또는 pivot으로 불림)

② 배열을 기준 원소보다 작은 원소의 배열과 큰 원소의 배열, 두 개의 하위 배열로 나눈다. (하위 배열들은 아직 정렬되어 있지 않은 상태)

③ 각 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다. 

④ ①~③을 반복하다가 하위 배열의 원소가 하나, 둘 혹은 없는 경우가 생기면, 위의 1) 또는 2)를 적용한다.

 

퀵 정렬의 실행시간을 빅오로 표기하면 평균적으로 O(n log n)의 시간이 걸린다. 하지만 최악의 경우 O(n²)의 시간이 걸릴 수도 있다. 퀵 정렬과 자주 함께 등장하는 병합 정렬도 역시 O(n log n)의 시간으로 동일하지만 퀵 정렬이 병합 정렬보다 더 작은 상수를 가진다는 차이가 있다. 보통 빅오로 표기할 때 상수가 영향을 끼치지 않기 때문에 무시하고 표기하는 경우가 많지만, 퀵 정렬과 병합 정렬은 동일한 실행시간을 가지고 있기 때문에 (퀵 정렬의 최악의 경우를 제외하고,, 실제로 일반적인 경우가 더 많다..ㅎ) 상수가 작은 퀵 정렬이 더 빠르다고 볼 수 있다.

 

 

■ 후기

 

실행시간은 배열이 가장 빨랐다. (위에서부터 LinkedList - ArrayList -  배열 순서)

 

전체 탐색의 경우인 만큼 다음 행선지(요소)를 분명히 알 수 있는 배열이나 링크드리스트가 빨랐던 것 아닐까싶다는....

 

 

 

 

 

 

 

잘못된 점이나 보충할 부분이 있으면 코멘트 남겨주세요

작은 조언이 저에겐 성장의 원동력이 됩니다 :-)

---

참고문헌 : Hello Coding 그림으로 개념을 이해하는 알고리즘