[코딩테스트 C++] 멀티탭 스케줄링

오늘의 문제

https://www.acmicpc.net/problem/1700

멀티탭 스케줄링

접근 방법

• 운영체제 지식이 이럴 때 도움이 된다. 캐시에서 좀 더 나가서 hit rate를 최대로 하기 위한 방법을 찾는 것
• 이미 스케줄이 나와있기 때문에 같은것이 다음에 나올 시간을 안다.
• 검색에 유리하도록 map에 문자와 다음에 나오는 idx를 저장한다.
• map에 없을 경우, map의 크기가 최대일 경우 vector로 옮긴 후 최대인 값(가장 뒤에 나올 값)을 삭제하고, 새로운것을 넣는다.
• 크기가 최대(n)가 아니라면 그냥 새로운것을 넣는다. 새로 넣을 때는 다음 idx를 검색해서 넣는다 없다면 INF
• map에 있을 경우, 새로운 value값으로 갱신한다.

나의 풀이

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#pragma warning(disable: 4996)
using namespace std;
const int INF = 987654321;

int n, k;

bool cmp(pair<char, int> a, pair<char, int> b){
    return a.second> b.second;
}
int findIdx(string s, int i){
    int ret=0;
    int idx = s.find(s.at(i), i+1);
    if(idx == -1)
        ret = INF;
    else
        ret = idx;
    return ret;
}
int main(){
    scanf("%d %d", &n, &k);
    map<char, int> m;
    string s = "";
    int c;
    for(int i=0;i<k;i++){
        scanf("%d", &c);
        s += '0'+c;
    }
    int answer = 0;
    for(int i=0;i<k;i++){
        if(m.find(s[i]) != m.end()){ // 찾음
            m[s[i]]= findIdx(s, i);
        }else{ // 못찾음
            if(m.size() == n){
                vector<pair<char, int>> vec(m.begin(), m.end());
                sort(vec.begin(), vec.end(), cmp);
                m.erase(vec[0].first);
                answer++;
            }
            m.insert(make_pair(s[i], findIdx(s, i)));
        }
    }
    cout<<answer<<endl;
    return 0;
}

다른 풀이

#include<stdio.h>
int n, k;
int u[102], o[102];
int us=0;
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++) scanf("%d", &o[i]);

	int cnt = 0;
	for (int i = 0; i < k; i++) {
		int j;
		for (j = 0; j < us; j++) {
			if (u[j] == o[i]) break;
		}
		if (j == n) {
			int maxi = 0,midx;
			int p;
			for (j = 0; j < us; j++) {
				for (p = i + 1; p < k &&o[p] != u[j]; p++);
				if (p > maxi) maxi = p, midx = j;
			}
			u[midx] = o[i];
			cnt++;
		}
		else if (j == us) u[us++] = o[i];
	}
	printf("%d", cnt);
	return 0;
}

배울 점

• 정말 잘 푼다. 이런 로직이 머리속으로 그려지는것이 부럽다. 열심히해야지