boj 2750 수 정렬하기

📌 how to solve

다양한 정렬 방식 중 어떤 방법을 써도 된다
필자는 버블 정렬 방식을 사용했다

💡 시간 초과(error code)

#include<stdio.h>
int main()
{
	int n = 0;
	int num[1024] = { 0 };
	scanf("%d", &n);
	for (int i = 0; i < n; i++) //배열에 수 정렬
		scanf("%d", &num[i]);
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
				int tmp = num[i];
				num[i] = num[j];
				num[j] = tmp;
		}
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d\n", num[i]);
	}
	return 0;
}

-분명히 버블 정렬을 찾아보고 코드를 그대로 짰는 데도 시간초과가 나와서 의문이
들었는 데 조금만 다시 생각해보니 문제점을 발견할 수 있었다

🧪 why?

		for (int i = 0; i < n-1; i++)
		{
			for (int j = i + 1; i < n; j++)
			{
				int tmp = num[i];
				num[i] = num[j];
				num[j] = tmp;
			}
		}

• 모든 경우에 tmp를 활용한 교환이 일어나서 시간이 많이 걸리고 불필요한 교환이 일어남
• 해결방법: if문으로 특정 부분만 교환하기
• ->오름차순 정렬이므로 num[i]>num[j]인 경우만 교환
  🧵 바꾼 코드

         for (int i = 0; i < n-1; i++)
		{
			for (int j = i + 1; i < n; j++)
			{
            if(num[i]<num[j])
				int tmp = num[i];
				num[i] = num[j];
				num[j] = tmp;
			}
		}

🔑 최종 code

#include<stdio.h>
int main()
{
	int n = 0;
	int num[1024] = { 0 };
	scanf("%d", &n);
	for (int i = 0; i < n; i++) //배열에 수 정렬
		scanf("%d", &num[i]);
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (num[i] > num[j])
			{
				int tmp = num[i];
				num[i] = num[j];
				num[j] = tmp;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		printf("%d\n", num[i]);
	}
	return 0;
}

🎉 후기

무작정 오름차순 정렬을 버블정렬로 구현하는 것만을 생각하고 풀었다가 시간초과가
나왔다
모든 경우를 컴퓨터가 수행해서 불필요한 시간이 소요되지 않도록 알고리즘을 짜도록 신경써야겠다