[C]백준 12.정렬: 2750

백준2750

내코드 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int arr[1001];
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}

정렬 단계에 수 정렬하기 문제는 총 3문제이다. 3문제 모두 오름차순으로 정렬하는 문제이지만 문제의 조건이 다 다르기 때문에 주의해야한다. 

 

문제 설명에서 "시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다." 이렇게 나와있길래 사실 바로 버블 정렬로 풀었지만 왜 시간복잡도가 O(n^2)인 정렬 알고리즘으로 풀 수 있는지 고민해 봤다.

 

수 정렬하기 중 첫번째인 이 문제의 조건을 살펴보면 정렬해야 하는 수의 개수가 1<=N<=1,000 이라는 조건을 갖고, 시간제한은 1초, 메모리 제한은 128MB이다. 

잘 알려진 정렬 방법인 버블정렬, 삽입정렬의 시간 복잡도는 O(n^2)이다. 버블정렬, 삽입정렬을 이용하면 최대 약 1,000,000번의 연산을 하고, 1초에 약 1~2억번 연산을 한다고 가정했을 때 1초를 넘기지 않으므로 시간적 측면에서 버블정렬, 삽입정렬은 가능하다.

또한 버블정렬과 삽입정렬은 코드에서 크기가 N인 int형(4바이트) 일차원 배열을 사용하기 때문에 N이 최대 1000이라면 4000바이트를 사용하게 되므로 메모리 측면에서도 문제가 없다. 

 

<참고 링크>

https://syh39.github.io/algorithm/algorithm_2/#%EC%B6%9C%EC%B2%98

백준 시간제한과 메모리제한