코딩테스트 -- 상담원 인원 - (프로그래머스 / C++)

 

 

프로그래머스

 

 

문제요약!

---

각 분야 별로 상담사들이 1명이상 있고, 분야별 참가자들이 시간에 따라 상담을 지원할때, 상담사들을 효율적으로 배치하여 참가자들의 대기 시간을 최소로 만들어야 하는 문제!

 

그리고 다음과 같은 조건들

1. 분야는 1~5가지가 있고 참가자는 300명, 상담사는 분야의 수~ 20명이 존재

2. 시작 시간은 1 ~ 1000분, 상담시간은 1~100분 

 

 

---

 

 

문제를 보고 처음 생각났던 방법은 DP를 이용한 풀이방법이였습니다.

각각의 분야별로 상담사의 명수에 따른 대기 시간의 총합을 저장하는 방법!

 

하지만... 분야가 5개... dp[1][2][3][4][5] ...? 어떻게 표현해야할지 막막해서 포기...

지금 생각해보니 vector에 dp[분야][배치된 상담사] 로 표현할 수 있었던것 같습니다!

그렇게 되면 분야별로 몇명을 배치해야 최대효율을 가지는지 쉽게 구할수 있겠네요...ㅠ

 

 

 

두번째는 완전탐색 방법이였습니다. 분야도 최대 5개, 멘토의 수도 20명 밖에 되지 않기에 충분히 가능하다고 생각하여 진행하였습니다!

 

그러다 모든 부분을 확인하지 않는 방법!

1. 처음엔 모든 분야에 1명씩 배치 (문제조건)

2. 기다린 시간이 제일 긴 분야에 멘토 +1 을 해주는 방법 (함수를 통해 배치될때마다 확인 최신화)

 

분야중 가장 대기시간이 길다 == 상담원이 필요하다!

 

위같이 생각하였을때 모든 부분을 확인하지 않아도 된다는것을 확인한 후 코드를 구성하였습니다.

 

 

 

 

그럼 코드 시작!

 

가장 먼저 현재 주어진 사람들을 분야에 따라 나누어 관리하기위한 List

각 분야별로 멘토수와 대기시간의 상태를 저장하는 vector를 선언했습니다.

vector<vector<pair<int, int>>> List;

vector<int> Mentor; // 각 분야의 멘토 수
vector<int>PartTime; // 각 분야별 기다린 시간

 

 

그리고 초기값들을 설정해 주었습니다.

int solution(int k, int n, vector<vector<int>> reqs) {
    int answer = 0;

    for (int i = 0; i < k; i++) { // 유형수
        List.push_back({});
        Mentor.push_back(1);
        n -= 1;
    }

    for (int i = 0; i < reqs.size(); i++) {
        List[reqs[i][2] - 1].push_back({ reqs[i][0],reqs[i][1] }); // 시작시간, 진행시간
    }

    for (int i = 0; i < k; i++) { // 각 분야별 초기 상태 
        PartTime.push_back(CalTime(i, 1));
    }
    
    TimeCheck(n);

 

여기서 TimeCheck 함수는 상담원을 배치하는  함수!

CalTime함수는 현재 멘토수에 대한 대기시간을 구해주는 함수입니다.

 

 

차례대로 TimeCheck 함수는 아래처럼 n명의 상담원을 배치하는것을 목표로 동작합니다.

단순 for문을 통해 현재 분야별 대기시간중 가장 오래 기다리는 분야를 구해 상담원을 추가 배치합니다.

void TimeCheck(int n) { // 남은 상담원, 멘토현재 분배 

    int answer = 0;
    int temp = 0;
    int tempInd = 0;
    int PartInit = 0;

    while (n) {

        answer = 0; // 현재 가장 기다린 시간이 긴 분야의 시간

        temp = 0;
        tempInd = 0;
        PartInit = 0;

        for (int j = 0; j < Mentor.size(); j++) { // 가장 기다린 시간이 긴 분야를 찾는부분
            temp = CalTime(j, Mentor[j] + 1); // 현재 분야의 기다린 시간

            if (answer < PartTime[j] - temp) {
                tempInd = j;
                answer = PartTime[j] - temp;
                PartInit = temp;
            }
        }

        PartTime[tempInd] = PartInit;
        Mentor[tempInd] += 1;
        n -= 1;
    }
}

 

 

CalTime함수에서는 현재 상담원의 수를 가지고 참가자들을 처리합니다. 그리고 대기시간들의 합을 리턴해줍니다.

int CalTime(int part, int n) { // 기다린 시간 체크 // 분야와 멘토 수  

    vector<int>MentorTemp;
    int delayTime = 0;
    int temp = 2000;
    int useMentor = 0;

    for (int i = 0; i < n; i++) { // 각 멘토의 현재시간
        MentorTemp.push_back(0);
    }

    for (int i = 0; i < List[part].size(); i++) { // 분야에 대한  참가자들

        temp = 2000;

        for (int j = 0; j < n; j++) {

            if (temp > MentorTemp[j]) {
                useMentor = j;
                temp = MentorTemp[j];
            }
        }

        if (MentorTemp[useMentor] == 0) {
            MentorTemp[useMentor] = List[part][i].first + List[part][i].second;// 첫번째 사람 ㅇㅇ
        }
        else {

            if (MentorTemp[useMentor] <= List[part][i].first) { // 시간이 남아 
                MentorTemp[useMentor] = List[part][i].first + List[part][i].second;
            }
            else { // 기다림...
                delayTime += (MentorTemp[useMentor] - List[part][i].first);
                MentorTemp[useMentor] += List[part][i].second;
            }
        }
    }
    return delayTime;

}

 

 

위와 같이 함수를 실행 해준후 상담원 배치와 함께 최신화되던 PartTime에 저장된 값들을 더해주면 최소 대기시간!

답을 얻을 수 있었습니다.

   for (int i = 0; i < k; i++) {
        answer += PartTime[i];
    }

    return answer;

 

 

DP방법으로 풀어내 보았다면 좀 더 간결해질 수도 있었겠지만, 위와 같은 방법도 나쁘지 않은 방법이였던것 같습니다.

 

DP코드는 추후에 새로 연구해보겠습니다.

 

 

 

 

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