문제1 , 수 정렬하기

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

 

입력

1번째 줄에 수의 개수 N(1<= N <= 1,000,000) 

2번째 줄부터는 1번째줄의 N개의 줄에 숫자가 주어진다.

이 수는 절대값이 1,000,000 보다 작거나 같은 정수이다.

수는 중복되지 않는다.

(절댓값 , 수학에서 절댓값(絶對-, 영어: absolute value 또는 modulus)은 실수나 복소수가 원점으로부터 떨어진 거리를 나타내는 음이 아닌 실수이다. )

출력

1번째 줄에서 N개의 줄에 오름차순 정렬된 결과를 1줄에 1개씩 출력한다.

(수를 입력받고 이에 중복을 제거하고 오름차순 정렬한다)

 

예

5 (N개의 숫자를 받겟다)

5

2

3

4

1

 

출력

1

2

3

4

5

 

1.시간복잡도는 총 데이터 범위를 봐야한다 (1,000,000)

연산횟수 계산하는 방법

연산횟수 = 알고리즘 시간복잡도 * 데이터의 크기

*각 알고리즘은 각기 시간복잡도를 가지고 있다. 

그래서 예를 들면

알고리즘에서 1초라는 정의는 1억 회 연산을 1초라 한다.

버블정렬 = N² 이니 (N = 1,000,000 * 1,000,000) = 1,000,000,000,000 > 200,000,000 = 2초(2억회)보다 높으니 부적합

병합정렬 = N = n lon n 이니 1,000,000 log (1,000,000) 약 2,000,000 < 200,000,000 = 적합 알고리즘

 

그래서 데이터 크기를 따져서 최적의 알고리즘을 사용해야 한다.

 

시간복잡도 도출 기준

1.상수는 시간복잡도 계산에서 제외한다.

2.가장 많이 중첩된 반복문의 수행횟수가 시간복잡도의 기준이 된다.

 

ex) 연산 횟수가 N인 경우

public class ex {

 public static void main(String[] args){

 int n = 100000;

 int cnt = 0;

 

 for (int i =0; i<N; i++){

 System.out.println(cnt);

 }

}

}

이 경우 최대 연산횟수는 N(100000) 

이때는 O(n) 이 된다.

 

ex)

n = 100000

for(int i = 0; i<N; i++){}

for(int i = 0; i<N; i++){}

for(int i = 0; i<N; i++){}

이렇게만 보면 10만번의 반복문이 3번 도는것처럼 보이며 3N 30만번 같지만

조건 1 상수 (이 경우는 100000)은 시간복잡도에서 제외하므로 3N이 아니라 N 이된다.

 

단 반복고문이 중첩되면 N2가 되기 떄문에 ON2가 된다,

int N = 100000;

int cnt = 0;

 

for(int i = 0; i < N ; i++){

 for(int j = 0 ; j < N ; j ++){

 

}

}

 

시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출 하므로

이 코드에서 이중 for문이 전체 코드의 시간복잡도의 기준이 왼다.

만약 일반 for문이 10개 더 있다 하더라고

도출원리 기준 2에 따라 시간복잡도의 변화없이 N2로 유지되게 된다,

 

이 말은 시간복잡도의 기준은 가장 중첩이 많이된 반복문이 기준이 된다,

 

1.알맞은 알고리즘 쓰기

2. 비효율 적인 로직을 찾아서 효율적으로 바꾸기,