구름톤 첼린지 5일차

#include <iostream>
using namespace std;

struct point
{
	int de;
	int bi;
};

int main() {
	int N, K, temp, cal;
	cin >> N >> K;
	int* arr = new int[N];
	
	point* sorted = new point[N];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		temp = arr[i];
		cal = 0;
		while (temp > 0)
		{

			if (temp % 2 == 0)
			{
				cal += 1;
			}
			temp = temp / 2;
		}
		sorted[i].bi = cal;
		sorted[i].de = arr[i];
	}

	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - i - 1; j++)
		{
			if (sorted[j].bi <= sorted[j + 1].bi)
			{
				if (sorted[j].bi == sorted[j + 1].bi)
				{
					if (sorted[j].de < sorted[j+1].de)
					{
						int temp = sorted[j].bi;
						sorted[j].bi = sorted[j + 1].bi;
						sorted[j + 1].bi = temp;

						temp = sorted[j].de;
						sorted[j].de = sorted[j + 1].de;
						sorted[j + 1].de = temp;
					}
				}
				else
				{
					int temp = sorted[j].bi;
					sorted[j].bi = sorted[j + 1].bi;
					sorted[j + 1].bi = temp;

					temp = sorted[j].de;
					sorted[j].de = sorted[j + 1].de;
					sorted[j + 1].de = temp;
			
				}

			}
			
		}
	}

	for (int i = 0; i < N; i++)
		cout << sorted[i].de << " ";

	cout << "\n";
	for (int i = 0; i < N; i++)
		cout << sorted[i].bi << " ";

	cout<<sorted[K].de;

	

}

내가 처음에 구현했던 코드

버블정렬을 사용했는데, \(O(n^2)\)이라서 그런지 테스트케이스 10 이후부터는 시간초과가 났다.

그래서 병합정렬이나 퀵정렬을 사용한다고 생각했는데

 

병합정렬 구현을 생각만해도 개같아서 안했다.

챗gpt한테 이거 시간을 줄여달라고 하니까 코드를 짜줬다.

 

#include <iostream>
#include <algorithm>
using namespace std;

struct point
{
    int de;
    int bi;
};

bool compare(const point& a, const point& b)
{
    if (a.bi != b.bi)
        return a.bi > b.bi;
    return a.de > b.de;
}

int main()
{
    int N, K;
    scanf("%d %d", &N, &K);

    point* sorted = new point[N];

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &sorted[i].de);
        int temp = sorted[i].de;
        sorted[i].bi = 0;
        while (temp > 0)
        {
            sorted[i].bi += (temp % 2);
            temp /= 2;
        }
    }

    sort(sorted, sorted + N, compare);

    printf("%d", sorted[K - 1].de);

    delete[] sorted;

    return 0;
}

존나 간단하게 푼다

현타가 온다

ㅠㅠ