1700. 멀티탭 스케줄링

phoenixKim·2022년 9월 27일

백준 알고리즘

목록 보기

134/174

첫번째 풀이 전략

각 인덱스마다 카운팅을 한후, 나타날때마다 차감을 해서
가장 작은 값이 있는 원소를 빼고, 그 자리에 새로운 값을 넣어주는 방식
으로함

결과

: 27퍼에서 틀림.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;

// 16:55

int cnt[101];
int main() 
{
	// 멀티탭 구멍의 개수 n과 전기 용품의 총 사용횟수 k가 주어짐.
	

	// 23
	// 32 -> no
	// 23 -> no
	
	// 1을 꽂기 전에 기존에 멀티탭에 잇는 것들 중에서 
	// 어떤 것을 뺄까가 가장 중요하.ㅁ

	// 12 31 ?
	// 뒤에 2가 나오므로 

	// 12로 가야함. 

	// 그 다음 : 2 : no
	// 7 -> ok

	// 1 2 3 7
	// 1 3 2 1
	// 카운팅을 하다가 카운팅이 가장 작은 것을 빼는 것이 최선이지
	// 않을까란? 생각을 함.

	// 1을 넣는 시점에서 
	// 1 2 3 7
	// 1 1 0 1 
	// 이므로 가장 작은 3을 빼자.


	// 이거를 어떻게 표현할 것이냐가 관건임. 
	// 2 3 
	// 1 을 넣기 전에 3을 빼자
	// 비트마스킹으로 해보자. 


	int n, k;
	cin >> n >> k;

	int bit = 0;

	int vv[101];
	for (int i = 0; i < k; ++i)
	{
		int num;
		cin >> num;
		vv[i] = num;
		cnt[num]++;
	}

	vector<int>v;
	int res = 0;
	for (int i = 0; i < k; ++i)
	{
		//cnt[i];
		cnt[cnt[i]]--;
		//auto iter = find(v.begin(), v.end(), cnt[i]);
		
		if (v.size() == n)
		{
			auto iter = find(v.begin(), v.end(), vv[i]);
			// 존재할 경우 패스
			if (iter != v.end())
				continue;

			// 이후에 카운팅된 값중에서 가장 작은 원소에 있는 것을 
			// erase 한 다음에 , 다음거를 push하자
			int ele = -1;
			int mmin = 1000;
			// 벡터에 있는 것중에서 가장 작은거를 찾아야 함.
			for (auto iter : v)
			{
				if (mmin > cnt[iter])
				{
					mmin = cnt[iter];
					ele = iter;
				}
				// 어떤 원소인지를 알아야 함.
			}
			auto iter1 = find(v.begin(), v.end(), ele);
			v.erase(iter1);
			v.push_back(vv[i]);
			++res;
		}
		else
		{		
			auto iter = find(v.begin(), v.end(), vv[i]);
			// 존재할 경우 패스
			if (iter != v.end())
				continue;
			v.push_back(vv[i]);
		}
		
		
	}

	printf("%d", res);
}