[백준알고리즘-JAVA]2751번 풀이(수 정렬하기2) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2751번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2751 (수 정렬하기 2)

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

입력 예시

5
5
4
3
2
1

출력 예시

1
2
3
4
5

성공코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	ArrayList<Integer> al = new ArrayList<Integer>();
	   	 	StringBuilder sb = new StringBuilder();
	   	 	
	   	 	for(int i = 0 ; i < num; i ++) {
	   	 		al.add(i,Integer.parseInt(br.readLine()));
	   	 	}
	   	 	
	   	 	Collections.sort(al);
	   	 	
	   	 	for(int i : al)
	   	 		sb.append(i).append("\n");
	   	 	
	   	 	System.out.println(sb);
	   	 	}
		}

수 정렬하기 2는 앞서 했던 수 정렬하기부터 시리즈별로 3개의 시리즈가 있음을 알 수 있습니다. 이전 시리즈인 수 정렬하기의 경우 시간이 O(n^2)의 시간 복잡도가 걸리는 경우이죠.

 

자 여기서 STEP을 넘 거 가기 전에 시간 복잡도와 정렬 방법에 대해서 알아보도록 합시다.

 

---

시간 복잡도

 

우리가 작성하는 모든 코드에는 해당 코드를 처리하기 위해 시간이 걸리게 됩니다. 그 시간을 나름의 기준을 통해 나누었습니다. 그 시간 복잡도는 굉장히 여러 종류가 있습니다. 상수 시간, 반복 로그 시간, 로그-로그 시간 등 굉장히 다양한 종류로 시간의 기준을 나누었습니다.

 

그중에

수 정렬하기 1 : 해당 알고리즘의 경우 O(n^2)의 시간 복잡도를 넘지만 않으면 성공할 수 있는 알고리즘

수 정렬하기 2 : 해당 알고리즘의 경우 O(nlongn)의 시간 복잡도를 넘지 않으면 성공할 수 있는 알고리즘

수 정렬하기 3 : 해당 알고리즘의 경우 O(n)의 시간 복잡도를 넘지 않으면 성공할 수 있는 알고리즘입니다.

 

그렇다면 이러한 시간 복잡도를 넘지 않는 알고리즘을 어떻게 구현해야 할까요?

 

그 방법은 바로 정렬 방법에 따라 시간 복잡도를 결정할 수 있기 때문에 이다음에 알아야 할 것은 바로 정렬 방법입니다.

 

---

정렬 방법

수많은 사람들이 다양한 방법으로 정렬을 하는 방법 이 있습니다. 이전에 우리가 살펴보았던 수 정렬하기 1의 경우 버블 정렬이라는 방법으로 해당 알고리즘을 해결해 나갔죠

 

버블 정렬이란 거품처럼 퍼져 있는 모양이라고 하여 지어진 이름이며, 시간 복잡도는 O(n^2)의 시간이 걸리게 됩니다.

 

왜냐하면 2중 반복문이 중첩된 경우입니다.

for( ~~ ){
	for(~~){
    ~~}
}

이런 식으로 2번이 반복문이 발생하면 n번을 돌면서 그 안에서 또 n번의 반복이 중첩이 되게 됩니다. 이전 수 정렬 시리즈를 통해서 해결했던 방법을 이번 알고리즘에 적용하게 되면 시간 초과라는 에러가 뜨게 됩니다!

 

 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬 등 수많은 정렬 방법이 있고 그에 따른 각자의 장단 점이 있고 해당 정렬을 이행하는 시간 복잡도를 가지게 됩니다.

 

그렇다면 저희는 각 정렬방법마다 어느 시간 복잡도를 가지는 지에 집중해야 합니다.

 

그중 유명한 정렬 5가지에 대해서 설명해 드리겠습니다.

 

선택 정렬 : 시간 복잡도 O(n) ~ O(n^2)

삽입 정렬 : 시간 복잡도 O(n) ~ O(n^2)

버블 정렬 : 시간 복잡도 O(n) ~ O(n^2)

합병 정렬 : 시간 복잡도 O(nlongn)

퀵 정렬 : 시간 복잡도 O(nlongn) ~ O(n^2)

 

여기서 범위를 같은 이유는 애초에 주어진 수 들이 정렬이 돼있을 경우 n번씩만 하면 되지만, 정 반대로 정렬되어 있다면 그에 상응하는 n^2의 시간만 큼이 걸리기 때문이죠

 

그러나 합병 정렬의 경우 어떤 값이 오도라도 nlogn의 시간이 걸리게 되죠

 

각 정렬에 대한 자세한 내용은 구글링을 해보시면 자세히 설명해 주신 곳이 많을 겁니다.

---

알고리즘 흐름도

입력받기 -> 받은 입력 정렬하기 -> 출력하기

---

STEP1 정렬하기

사실 해당 코드는 시간 복잡도와 정렬 방법에 대해서 알고 있다면, 쉽게 해결할 수 있는 알고리즘입니다.

 

이전에 사용했던 

Array.sort()의 경우 시간 복잡도가 O(n) ~ O(n^2)의 범위가 됩니다. 왜냐하면 자바에서 이미 만들어둔 배열 정렬 메서드의 경우 많은 정렬 중에 tim 정렬이라는 방법을 택하여 정렬해줍니다. 이때 tim정렬이 해당 시간 복잡도를 가지기 때문이죠

 

그러나 Collections.sort()의 경우 삽입 정렬과 합병 정렬을 병합적으로 사용하여 최선의 시간으로 도출하게 됩니다 따라서 시간 복잡도는 O(n) ~ O(nlogn)의 시간 복잡도를 가지게 되죠

 

이에 따라서 저희는 컬렉션을 이용하여 입력받은 값을 이용해서 해당 메서드를 이용해 구현한다면 쉽게 해결할 수 있게 됩니다.

for(int i = 0 ; i < num; i ++) {
	   	 		al.add(i,Integer.parseInt(br.readLine()));
	   	 	}
	   	 	
	   	 	Collections.sort(al);
	   	 	
	   	 	for(int i : al)
	   	 		sb.append(i).append("\n");
	   	 	
	   	 	System.out.println(sb);

간단합니다. 처음 입력받은 만큼 반복해주면서 ArrayList <integer> al 변수에 입력값을 하나씩 넣어준 뒤 Collections.sort 메서드를 이용해 정렬한 후 StringBuilder를 통해 값을 넣어주어 출력하면 끝!

 

여기서 반복문을 이용해 바로 System.out.println을 사용할 경우 입력이 많아지면, 시간 복잡도에 영향을 주어 시간 초과가 날 수 있습니다! (이거는 그냥 println의 특성이라고 알아두시면 됩니다.)

 

여기서 어? 저기 다른 반복문들이 있는데 이 시간 복잡도는 신경을 안 쓰나? 하는 의문이 드실 겁니다.

 

저도 정확히 알지는 못하지만, 가장 큰 시간 복잡도 외에는 값이 커질수록 무의미해지기 때문에 가장 큰 값을 시간 복잡도로 지정한다고 알고 있습니다!