코딩테스트 -- 선입 선출 스케줄링 - (프로그래머스 / C++)

 

프로그래머스

 

문제!

---

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

 

---

요약하면 코어별로 작업을 부여할때 마지막 작업이 시행된 코어의 번호를 출력하는 문제!

 

 

간단해보이지만 당연히! 10000개짜리 배열로 문제대로 탐색을 진행하면 시간초과난다 ㅋㅋ

 

실패

#include <string>
#include <vector>

#include<iostream>
using namespace std;

int solution(int n, vector<int> cores) {
    int answer = 0;
    int core_m[10001]={0};
    
    if(n<=cores.size()){
        return cores.size()-1;
    }
    else{
        for(int i=0;i<cores.size();i++){
            core_m[i]=cores[i];
            answer=i;
        }
    }
    n-=answer+1;
    
    while(true){
        
        if(n==0){
            break;
        }
        
        for(int i=0;i<cores.size();i++){//하나씩 빼주기
            if(core_m[i]!=0){
               core_m[i]-=1; 
            }
        }
        
       for(int i=0;i<cores.size();i++){//빈거 찾기
           if(core_m[i]==0){
               core_m[i]=cores[i];
               answer=i;
               n-=1;
               if(n==0){
                    break;
                }
           }
       }
    }
    
    return answer+1;
}

 

그럼 어떻게 해야할까!

 

진짜 생각지도 못했는데 이분탐색을 사용하네요;;;

 

 

 

 

이해가 좀 어렵긴 한데 그래도 시작!

 

 

일단 선언과 초기화 

int lo = 1, hi = 100000000;
    
    while(lo+1 < hi) {//이분탐색
        int mid = (lo+hi)/2;
        int cnt = 0;
        vector<int> memo;//항상 초기화

여기서 약간 이상한점이 있지 않나요..?

 

 

최댓값이 왜 1000000 일까?

원래는 50000 * 10000 / 2 = 250000000 인데 이걸 풀어낼수가 없더라구요;; 

(하지만.. 테스트 케이스 부족으로 100000000으로 설정해도 통과... 실제론 틀린코드)

 

보고 이해로만 사용해주세요!

 

 

 

다음은 매번 현재 mid시간까지 수행한+수행하는중 인 작업의 수와 끝난 작업의 수를 구해 계산해줍시다.

for(int i = 0;i < cores.size();++i) {
            cnt += mid/cores[i]+1;//지금까지 수행한 + 하는중 작업 수
            if(mid % cores[i] == 0){//이번 mid 시간에 끝나는것들 저장
                memo.push_back(i);
                cnt -= 1;
            }
        }

 

 

 

그리고 n과 비교하여 이분탐색을 완료 해줍시다!

if(cnt >= n){//작업 과다
            hi = mid - 1;
        } 
        else if(cnt + memo.size() < n){//작업 부족
            lo = mid + 1;
        }
        else{
            return memo[n - cnt - 1] + 1;// 적절값! 마지막 메모값 리턴
        }

 

 

위에서 말했던 문제가 있어 코드를 하나더 보았지만 이마저도 마찬가지네요...

 

 

 

ALL 1

#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> cores) {
    int lo = 1, hi = 100000000;
    
    while(lo+1 < hi) {//이분탐색
        int mid = (lo+hi)/2;
        int cnt = 0;
        vector<int> memo;//항상 초기화
        
        for(int i = 0;i < cores.size();++i) {
            cnt += mid/cores[i]+1;//지금까지 수행한 + 하는중 작업 수
            if(mid % cores[i] == 0){//이번 mid 시간에 끝나는것들 저장
                memo.push_back(i);
                cnt -= 1;
            }
        }
        
        if(cnt >= n){//작업 과다
            hi = mid - 1;
        } 
        else if(cnt + memo.size() < n){//작업 부족
            lo = mid + 1;
        }
        else{
            return memo[n - cnt - 1] + 1;// 적절값! 마지막 메모값 리턴
        }
    }
}

 

 

ALL2

#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;
int solution(int n, vector<int> cores) {
    long long lo=1;
    long long hi=100000001;
    long long mid=0;

    while(lo+1<hi){//이분탐색-- > 총 시간에서 각각의 작업시간을 나눠준 몫들의 합 == n 이 될때까지
        mid = (lo+hi)/2;
        long long cnt=cores.size();
        
        
        for(int i=0;i<cores.size();i++){
            cnt+=mid/cores[i];
        } 
        
        if(cnt<n){
            lo=mid;
        } 
        else{
            hi=mid;
        }
        //cout<<mid<<","<<lo<<","<<hi<<endl;
        
    }
    
    long long cnt=cores.size();
    
    for(int i=0;i<cores.size();i++){
        cnt+=lo/cores[i];// lo 까지 진행될 작업수
    } 
    
    for(int i=0;i<cores.size();i++){
        if((lo+1)%cores[i]==0){// lo+1 시간에 딱맞게 처리되는것 찾기
            cnt++;
        } 
        if(cnt==n){
            return i+1;
        } 
    }
    
    return 0;
}

 

 

[프로그래머스][level4] 선입 선출 스케줄링 (C++)

 

 

 

이번 문제 먼가 찝찝하지만 이분탐색 연습문제였다고 생각하고 복습해야겠네요!

 

 

 

틀린점이 있다면 댓 달아주세요!