boj 9076 점수 집계

📌 how to solve

• 심판들의 점수를 배열에 저장, num[5]
• 심판들의 점수를 내림차순으로 정렬
• 최고점과 최저점을 제외한 점수의 합 출력
• 2, 4번째 점수차이가 4이상이라면 KIN 출력

🧪 시간초과

#include<stdio.h>
int main()
{
	int t = 0;
	scanf("%d", &t);
	int sum = 0;
	for (int i = 0; i < t; i++)
	{
		sum = 0;
		int jumsu[6] = { 0 };
		for (int i = 0; i < 5; i++)
		{
			for (int j = i + 1; i < 6; j++)
			{
				int tmp = jumsu[i];
				jumsu[i] = jumsu[j];
				jumsu[j] = tmp;
			}
		}
		if (jumsu[1] - jumsu[3] >= 4)
		{
			printf("KIN\n");
			continue;
		}
		else
		{
			printf("%d\n", jumsu[1] + jumsu[2] + jumsu[3]);
		}
	}
	return 0;
}

• 왜 시간초과가 났을까?

💡 why?

		for (int i = 0; i < 5; i++)
		{
			for (int j = i + 1; i < 6; j++)
			{
				int tmp = jumsu[i];
				jumsu[i] = jumsu[j];
				jumsu[j] = tmp;
			}
		}

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

🔑 code

#include <stdio.h>
int main() 
{
    int n = 0;
    int num[5] = { 0 };
    int tmp;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
    {
        int sum = 0;
        for (int j = 0; j < 5; j++) 
        {
            scanf("%d", &num[j]);
        }


        for (int k = 0; k < 5; k++) {
            for (int m = 0; m < 5; m++) 
            {
                if (num[k] > num[m]) 
                {
                    tmp = num[k];
                    num[k] = num[m];
                    num[m] = tmp;


                }
            }
        }
        if (num[1] - num[3] >= 4) 
            printf("KIN\n");
        else 
            printf("%d\n", num[3] + num[2] + num[1]);
    }
    return 0;
}

🎉 후기

거품정렬에 대해 정확히 알지 못하고 코드를 짰더니 교환을 최소화하는 조건을 생각하지 않고 짜 시간초과가 났다
최댓값과 최솟값을 활용하여 조건을 더 줄일 수도 있을 것 같으니 다음에 해봐야 겠다