[알고리즘, 틀림] 백준 1700 멀티탭 스케쥴링 // 그리디, 페이지 교체 알고리즘

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

* 풀이1

 

• vector, 배열에 삽입, 삭제 불편 -> unorder_set사용 (find O(1)임)
  • find후 없으면 s.end를 리턴함

• 최초로 찾은후 break 해야하는 이유

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,k,ret;
unordered_set<int> s;
int arr[104];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n>>k;

   for(int i=0;i<k;++i) {
      cin>>arr[i];
   }

   for(int i=0;i<k;++i) {
      int cur = arr[i];

      //이미 있음
      if(s.find(cur)!=s.end()) {
         continue;
      }

      // 빈공간이 있음
      if(s.size()<n) {
         s.insert(cur);
         continue;
      }

      //이미없고, 빈공간도 없음
      //현재 들어있는것중, 가장 먼 미래에 참조되는 애를 찾아 제거
      
      int target; // 제거대상
      int target_idx=-1; //제거대상의 인덱스
      
      for(auto plug : s) {
         int nxt_use=k; // 초기값 : 가장 먼 미래에 사용, 
         
         for(int j=i+1;j<k;++j) {
            if(arr[j]==plug) { // cur아님!, 탐색대상 : 현재들어있는것들(plug)
               nxt_use = j;
               break; //?
            }
         }
         // 제거대상의 인덱스보다, 현재 조사중인 plug가 더 미래에 참조된다면 그걸제거
         if(target_idx < nxt_use) {
            target=plug;
            target_idx=nxt_use;
         }
      }
      s.erase(target);
      s.insert(cur);
      ret++;
   }
   
   cout<<ret;
   
   return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K;  // N: 멀티탭 구멍 수, K: 전기용품 사용 횟수
    cin >> N >> K;
    
    int cnt = 0;  // 플러그를 뽑은 횟수
    vector<int> a(K);  // 전기용품 사용 순서
    unordered_set<int> plugged;  // 현재 꽂혀있는 전기용품들
    
    // 사용 순서 입력 받기
    for(int i = 0; i < K; i++) cin >> a[i];
    
    // 각 전기용품에 대해 처리
    for(int i = 0; i < K; i++) {
        int current = a[i];  // 현재 꽂으려는 전기용품
        
        // 이미 꽂혀있으면 스킵
        if(plugged.find(current) != plugged.end()) continue;
        
        // 멀티탭에 빈 구멍이 있으면 그냥 꽂기
        if(plugged.size() < N) {
            plugged.insert(current);
            continue;
        }
        
        // 여기부터는 멀티탭이 가득 찬 경우의 처리
        int latest = -1;     // 제거할 플러그 번호
        int latest_idx = -1; // 제거할 플러그의 다음 사용 시점
        
        // 현재 꽂혀있는 모든 플러그들 검사
        for(auto plug : plugged) {
            int next_use = K;  // 현재 검사중인 플러그의 다음 사용 시점
                              // K로 초기화 = 더 이상 사용되지 않음을 의미
            
            // 현재 시점(i) 이후부터 이 플러그의 다음 사용 시점 찾기
            for(int j = i + 1; j < K; j++) {
                if(a[j] == plug) {
                    next_use = j;  // 다음 사용 시점 발견
                    break;
                }
            }
            
            // [핵심] 이 플러그가 지금까지 찾은 것보다 더 나중에 사용되면
            if(next_use > latest_idx) {
                latest = plug;      // 이 플러그를 제거 대상으로 저장
                latest_idx = next_use;  // 가장 나중 사용 시점 갱신
            }
        }
        
        // 가장 나중에 사용될 플러그를 제거하고
        plugged.erase(latest);
        // 새 플러그 꽂기
        plugged.insert(current);
        cnt++;  // 플러그를 뽑았으므로 카운트 증가
    }
    
    cout << cnt << '\n';
    return 0;
}