[백준] 1700 멀티탭 스케쥴링 (C++ - 그리디 알고리즘)

💡 멀티탭 스케쥴링 info

• 문제 제목 : 멀티탭 스케쥴링
• 문제 번호 : 1700
• 난이도 : 골드 I (정답률 : 26.4%)

👀 문제 설명

멀티탭 구멍의 개수가 주어지고, 전기 용품의 사용 순서가 주어질 때,
최대한 플로그 뽑는 횟수를 적게하여 그 횟수를 출력해내면 된다.

예시

• 멀티탭 구멍의 개수 : 3
• 사용하는 전자기기 순서 : 키보드 > 드라이기 > 충전기 > 커피포터 > 키보드 > 드라이기
  이때 키보드, 드라이기, 충전기의 플러그를 순서대로 꽂은 후,
  나중에 다시 사용하지 않는 충전기 플러그를 뺀 후, 커피포터 플러그를 꽂으면 된다.
  => 총 1번만 빼면 된다.

입력 : 멀티탭 구멍의 개수 N, 전기 용품의 총 사용횟수 K, 전기용품의 이름과 사용순서

2 7
2 3 2 3 1 2 7

출력 : 플러그를 빼는 최소의 횟수

🔨 해결 방법

상황을 3가지로 나누어서 판단하면 된다.
1. 사용할 전자기기 플러그가 이미 꽂혀 있을 때
2. 플러그를 꽂을 빈 자리가 있을 때
3. 빈 자리가 없을 때

꼭 3가지 경우를 순서대로 판단해야한다.
🚨 만약 멀티탭 구멍이 3개고, ( 물건1, 물건2, [빈자리] )라고 했을 때 사용할 물건이 물건1이라면 빈자리가 아니라 그냥 넘겨야할 상황이기 때문!

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
int N, K; // 멀티탭 구멍의 개수, 전기용품의 총 사용횟수
cin >> N >> K;

int *order = new int[K]; // 순서 받기
for (int i=0; i<K; i++) {
    cin >> order[i];
}

int *tap = new int[N]; // 멀티탭 배열
for (int k=0; k<N; k++) {
    tap[k] = 0;
  }

  int cnt = 0;
  for (int j=0; j<K; j++) {
      bool pass = false;
      // 이미 꽂혀있는지 확인
      for (int i=0; i<N; i++) {
          if (order[j] == tap[i]) {
              pass = true;
              break;
          }
      }
      if (pass) continue;

      // 빈 곳이 있는지 확인
      for (int i=0; i<N; i++) {
          if (tap[i] == 0) {
              tap[i] = order[j];
              pass = true;
              break;
          }
      }
      if (pass) continue;

      // 그 외
      int pos = -1; // 멀티탭에서 뺄 자리
      int idx = -1; // schedule이 가장 나중에 잡혀있는 것
      for (int i=0; i<N; i++) { // 멀티탭 번아 가면서 확인
          int tmp = 0; // 순서를 확인해야하므로
          for (int k=j+1; k<K; k++) { 
              if (tap[i] == order[k]) break; // 그 다음 스케줄 중에 멀티탭에 꽂혀있는 전자기기가 잡혀있다면
              tmp++;
          }
          if (tmp > idx) {
              pos = i;
              idx = tmp;
          }
      }
      tap[pos] = order[j];
      cnt++;
  }
  cout << cnt;
  return 0; 
 }
  

• tap[] : 멀티탭 구멍
• order[] : 스케쥴러

1. 이미 꽂혀있는 전자기기라면 pass

   for (int i=0; i<N; i++) {
     if (order[j] == tap[i]) {
         pass = true; // 그냥 넘기기
         break;
     }
   }
   if (pass) continue;

2. 빈 곳이 있다면 빈 곳 사용

   for (int i=0; i<N; i++) {
     if (tap[i] == 0) {
         tap[i] = order[j]; // 빈 곳에 해당 전자기기 꽂기
         pass = true; // pass
         break;
     }
   }
   if (pass) continue;  

3. 빈 곳이 없으면 가장 나중에 사용하는 전자기기 플러그 뽑기

   int pos = -1; // 멀티탭에서 뺄 자리
   int idx = -1; // schedule이 가장 나중에 잡혀있는 것
   for (int i=0; i<N; i++) { // 멀티탭 번아 가면서 확인
       int tmp = 0; // 순서를 확인해야하므로
       for (int k=j+1; k<K; k++) { 
           if (tap[i] == order[k]) break; // 그 다음 스케줄 중에 멀티탭에 꽂혀있는 전자기기가 잡혀있다면
           tmp++;
       }
       if (tmp > idx) {
           pos = i;
           idx = tmp;
       }
   }
   tap[pos] = order[j];
   cnt++;

   

   위 상황은 2, 3번이 꽂혀있고, 1을 사용할 차례이다. 이때 3이 더 나중에 사용하므로 3을 뽑는다.

   
   위 상황은 2, 3번이 꽂혀있고, 1을 사용할 차례이다. 이때 꽂혀있는 3을 더이상 사용하지 않을 것이므로 3을 뽑는다.