[백준 C++] 1700번 : 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

풀이 :

1. 멀티탭에 이미 꽂혀있는 용품은 고려하지 않는다.

2. 현재 필요한 용품이 꽂혀있지 않다면 이미 꽂혀있는 용품을 하나 빼야 한다.

      이때 카운트를 해준다.

3. 이미 꽂혀있는 용품이 뒤에 쓰이지 않는다면 그 용품부터 뺀다.

4. 이미 꽂혀있는 모든 용품을 뒤에 써야 한다면 가장 나중에 쓰는 용품을 뺀다.

 

코드보면서 설명 :

int n, k, arr[105], ans, index, flag_index, flag;
    set<int> s;
    set<int>::iterator iter;

    ans = 0;
    cin >> n >> k;
    for(int i=0; i<k; i++){
        cin >> arr[i];
    }
    for(int i=0; i<k; i++){
        if(s.size() == 0 || s.count(arr[i]) == 0){
            s.insert(arr[i]);
            index = i;
        }
        if(s.size() == n){
            break;
        }
    }

- 중복체크를 위해 set선언

 

- 두번째 for문은 멀티탭의 갯수(n)만큼 set에 넣어주는 과정

 

- 첫번째 if문을 통해 set에 들어있지 않다면 용품을 넣어준다

        index에 i값을 넣어줌으로 이후에 중복 탐색을 막는다

 

- 두번째 if문을 통해 set의 크기가 n과 같다면 즉, 멀티탭이 꽉 차게 되면 for문을 종료한다

 

for(int i=index+1; i<k; i++){
        if(s.count(arr[i]) == 0){
            flag = -1;
            flag_index = -1;
            for(iter = s.begin(); iter!=s.end(); iter++){
                for(int j=i+1; j<k; j++){
                    if(*iter == arr[j]){
                        flag = 1;
                        if(flag_index < j){
                            flag_index = j;
                        }
                        break;
                    }else{
                        flag = 0;
                    }
                }
                if(flag == 0){
                    s.erase(iter);
                    break;
                }
            }
            if(flag == 1){
                for(iter = s.begin(); iter!=s.end(); iter++){
                    if(*iter == arr[flag_index]){
                        s.erase(iter);
                        break;
                    }
                }
            }
            ans++;
            s.insert(arr[i]);
        }
    }
    cout << ans << endl;

- 먼저 아까 구해준 index+1부터 탐색을 시작한다

 

- if(s.count(arr[i]) == 0) : 현재의 값이 set에 있다면 무시되는 조건문

 

- if문에 들어갈 때마다 flag, flag_index의 값을 초기화해준다

 

- set에 들어있는 값을 기준으로 뒤에 나오는 값을 탐색한다

 

- if(*iter == arr[j]) : set에 들어있는 값이 뒤에 등장하는 경우

     flag에 1을 넣어서 중복됨을 표시한다

     if(flag_index < j) : set에 들어있는 여러 값이 뒤에 나온다면 그 중 마지막에 등장하는 값을 삭제하기 위한 부분

     찾자마자 break를 해서 찾고 있는 값이 여러번 나와도 제일 처음 등장했을 때의 index값만 비교할 수 있도록 한다

 

- else{ flag = 0;} : set에 있지만 뒤에 등장하지 않는 경우

    -> 가장 먼저 삭제해줘야 하는 값

    if(flag == 0)을 통해 삭제해주고 break 한다

 

- if(flag == 1) : set에 들어있는 모든 값이 뒤에도 등장한다는 뜻

   -> flag_index에 저장해준 index값과 일치하는 값을 set에서 삭제한다

 

- 조건문에 들어올 때마다 ans++과 set에 현재 값을 넣어준다

 

 - 마지막에 ans 출력하고 끝

 

전체 코드 :

#include <iostream>
#include <algorithm>   
#include <set>

using namespace std;

int main(){
    int n, k, arr[105], ans, index, flag_index;
    set<int> s;
    int flag;
    set<int>::iterator iter;

    ans = 0;
    cin >> n >> k;
    for(int i=0; i<k; i++){
        cin >> arr[i];
    }
    for(int i=0; i<k; i++){
        if(s.size() == 0 || s.count(arr[i]) == 0){
            s.insert(arr[i]);
            index = i;
        }
        if(s.size() == n){
            break;
        }
    }
    for(int i=index+1; i<k; i++){
        if(s.count(arr[i]) == 0){
            flag = -1;
            flag_index = -1;
            for(iter = s.begin(); iter!=s.end(); iter++){
                for(int j=i+1; j<k; j++){
                    if(*iter == arr[j]){
                        flag = 1;
                        if(flag_index < j){
                            flag_index = j;
                        }
                        break;
                    }else{
                        flag = 0;
                    }
                }
                if(flag == 0){
                    s.erase(iter);
                    break;
                }
            }
            if(flag == 1){
                for(iter = s.begin(); iter!=s.end(); iter++){
                    if(*iter == arr[flag_index]){
                        s.erase(iter);
                        break;
                    }
                }
            }
            ans++;
            s.insert(arr[i]);
        }
    }
    cout << ans << endl;
}

후기 :

풀이법은 어렵지 않게 생각했는데 구현이 어려웠다.

flag를 처음에는 bool로 선언하고 true, false 값에 따라서만 움직였었는데,

그렇게 했을 때 set에는 들어있지만 뒤에 등장하지 않는 값을 알아낼 수 없었다.

또한, flag_index를 초기화하는 코드가 set을 탐색하는 for문 안에 있었는데,

내가 구상한대로 최댓값을 비교할 수 없었던 오류가 있었다.

다만 이렇게 해도 예제는 다 맞고, 내가 생각했던 예제도 다 맞았어서 오류를 발견하기 어려웠다.

무작위로 예제를 넣다가 이전에 문제 풀 때도 초기화 과정에서 오류가 발생했었기 때문에,

이번에도 그런게 아닐까 하면서 한줄 한줄 다시 한번 검토했고, 오류를 수정할 수 있었다.