상담원 인원[Algorithm]

SnowCat·2023년 10월 17일
CS알고리즘완전탐색
0

CS - Algorithm

목록 보기
4/5
post-thumbnail

문제

문제 설명

현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.

참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.

  • 상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
  • 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
  • 모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.

참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.

예를 들어, 5명의 멘토가 있고 1~3번의 3가지 상담 유형이 있을 때 아래와 같은 참가자의 상담 요청이 있습니다.

참가자의 상담 요청

참가자 번호시각상담 시간상담 유형
1번 참가자10분60분1번 유형
2번 참가자15분100분3번 유형
3번 참가자20분30분1번 유형
4번 참가자30분50분3번 유형
5번 참가자50분40분1번 유형
6번 참가자60분30분2번 유형
7번 참가자65분30분1번 유형
8번 참가자70분100분2번 유형

이때, 멘토 인원을 아래와 같이 정하면, 참가자가 기다린 시간의 합이 25로 최소가 됩니다.

1번 유형2번 유형3번 유형
2명1명2명

1번 유형

1번 유형을 담당하는 멘토가 2명 있습니다.

  • 1번 참가자가 상담 요청했을 때, 멘토#1과 10분~70분 동안 상담을 합니다.
  • 3번 참가자가 상담 요청했을 때, 멘토#2와 20분~50분 동안 상담을 합니다.
  • 5번 참가자가 상담 요청했을 때, 멘토#2와 50분~90분 동안 상담을 합니다.
  • 7번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 5분 동안 기다리고 멘토#1과 70분~100분 동안 상담을 합니다.
    2번 유형

2번 유형을 담당하는 멘토가 1명 있습니다.

  • 6번 참가자가 상담 요청했을 때, 멘토와 60분~90분 동안 상담을 합니다.
  • 8번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 6번 참가자의 상담이 끝날 때까지 20분 동안 기다리고 90분~190분 동안 상담을 합니다.

3번 유형

3번 유형을 담당하는 멘토가 2명 있습니다.

  • 2번 참가자가 상담 요청했을 때, 멘토#1과 15분~115분 동안 상담을 합니다.
  • 4번 참가자가 상담 요청했을 때, 멘토#2와 30분~80분 동안 상담을 합니다.

상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • 1 ≤ k ≤ 5
  • k ≤ n ≤ 20
  • 3 ≤ reqs의 길이 ≤ 300
    • reqs의 원소는 [a, b, c] 형태의 길이가 3인 정수 배열이며, c번 유형의 상담을 원하는 참가자가 a분에 b분 동안의 상담을 요청했음을 의미합니다.
    • 1 ≤a ≤ 1,000
    • 1 ≤ b ≤ 100
    • 1 ≤ c ≤ k
    • reqs는 a를 기준으로 오름차순으로 정렬되어 있습니다.
    • reqs 배열에서 a는 중복되지 않습니다. 즉, 참가자가 상담 요청한 시각은 모두 다릅니다.

입출력 예

knreqsresult
35[[10, 60, 1], [15, 100, 3], [20, 30, 1], [30, 50, 3], [50, 40, 1], [60, 30, 2], [65, 30, 1], [70, 100, 2]]25
23[[5, 55, 2], [10, 90, 2], [20, 40, 2], [50, 45, 2], [100, 50, 2]]90

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

참가자의 상담 요청

참가자 번호시각상담 시간상담 유형
1번 참가자5분55분1번 유형
2번 참가자10분90분1번 유형
3번 참가자20분40분1번 유형
4번 참가자50분45분1번 유형
5번 참가자100분50분1번 유형

멘토 인원을 아래와 같이 정하면, 참가자가 기다린 시간의 합이 90으로 최소가 됩니다.

1번 유형2번 유형
1명2명

1번 유형

1번 유형을 담당하는 멘토가 1명 있습니다. 1번 유형의 상담을 요청한 참가자가 없지만, 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.

2번 유형

2번 유형을 담당하는 멘토가 2명 있습니다.

  • 1번 참가자가 상담 요청했을 때, 멘토#1과 5분~60분 동안 상담을 합니다.
  • 2번 참가자가 상담 요청했을 때, 멘토#2와 10분~100분 동안 상담을 합니다.
  • 3번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 40분 동안 기다리고 멘토#1과 60분~100분 동안 상담을 합니다. 1번 참가자의 상담이 끝났을 때 4번 참가자도 기다리고 있었지만, 먼저 상담 요청한 3번 참가자가 우선됩니다.
  • 4번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 2번 참가자의 상담이 끝날 때까지 50분 동안 기다리고 멘토#2와 100분~145분 동안 상담을 합니다. 이때, 멘토#1과 상담할 수도 있지만 어느 멘토와 상담해도 상관없습니다.
  • 5번 참가자가 상담 요청했을 때, 멘토#1과 100분~150분 동안 상담을 합니다.

따라서 90을 return 하면 됩니다.

접근법

  • 처음 문제를 읽으면서 입국 심사 문제처럼 이분 탐색을 사용해야하는 문제인가 생각했다.
  • 하지만 제한사항의 범위가 매우 짧기 때문에 그럴 필요없이 완전 탐색(=노가다)를 사용해서 답을 찾아도 된다.
  • 참가자가 기다리는 시간은 각 유형의 멘토 수에 의해서만 영향을 받는다. 따라서 멘토 수를 정할 수 있다면, 참가자가 기다리는 시간의 합은 항상 일정하다.
  • 이 사실을 바탕으로 해서 문제를 풀기위해 3단계로 문제를 접근했다.
    • 우선 각 유형별로 멘토 수에 따른 기다리는 시간을 담은 2차원 배열을 구한다.
    • 멘토를 각 유형에 배분해주는 모든 경우의 수를 구한다.
    • 각 경우의 수별로 대기시간을 구하고, 그 중 가장 작은 값을 반환한다.
  • 각각을 구현하는 난이도가 높지는 않지만, 코드가 길어지기 때문에 각 단계의 로직을 검토해 실수하지 않도록 유의한다.

풀이

멘토 수에 따른 대기시간 구하기

  • 각 유형별 상담 요청 배열을 받아, 해당 유형의 상담원 수가 주어지면 대기 시간을 반환하는 함수를 작성해야 한다.
  • 여러가지 방법이 있겠지만, 시간을 1분씩 돌려가면서 현재 상담을 받아야하는 사람과, 상담중인 사람이 있는지를 체크하였다.
    • 1분이 지날때마다 우선 상담이 종료된 사람이 있는지 확인하고, 확인하면 현재 상담중인 사람의 수를 줄여준다. 그래야 상담이 끝나자마자 새로운 사람이 바로 상담을 받을 수 있다.
    • 이후 상담을 받을사람이 있는지 확인한다.
    • 상담을 받을 사람이 있고, 상담을 받을 수 있다면, 현재 상담중인 사람의 수에 더한다. 상담이 동시에 종료되는 등의 이유로 한번에 2명이상의 사람이 동시에 상담을 시작할 수도 있기 때문에 상담을 받을 사람이 없거나, 상담을 받을 수 없는 상황이 될때까지 반복문을 계속 진행한다.
    • 상담을 받을 사람은 있지만, 멘토가 모두 상담중인 경우 현재 대기중인 상담인원수만큼 대기시간을 추가하고 현재시간을 1분 더해준다.
    • 상담을 받을사람이 없다면 현재시간을 1분 더해준다.
  • 이를 마지막 사람이 상담에 들어가는 순간, 즉 더이상 대기시간이 늘어날 수 없는 상황이 될때까지 반복하고, 대기시간을 반환한다.
// 각 유형별 상담 요청 배열과, 해당 유형의 상담원 수를 입력으로 받아 총 대기시간을 구하는 함수
const getTime = (reqArray, consultNum) => {    
    let currentTime = 0; // 현재 시간을 담는 변수
    let waitTimeSum = 0; // 총 대기시간을 담는 변수
    let index = 0; // 현재 대기중인 사람중 가장 먼저 상담을 받을 사람의 인덱스
    const consultEndArray = []; // 현재 상담을 받는 사람의 종료 시각을 담은 배열
        
  // 마지막 사람이 상담을 받기 시작한 순간 더이상의 대기는 발생하지 않게 됨
    while (index < reqArray.length) {
      // 상담이 종료된 순간 consultEndArray에서 해당 상담 종료시각값을 제거함
        while (consultEndArray.length > 0) {
            if (currentTime >= consultEndArray[consultEndArray.length - 1]) consultEndArray.pop();
            else break;
        }
            
      // 상담시작 시각과 상담 시간 가져오기
        const [a, b] = reqArray[index];

      // 상담시간이 되었고, 상담이 가능한 경우에는 상담 종료 시각을 consultEndArray에 넣고 인덱스를 1 올림
        if (currentTime >= a && consultEndArray.length < consultNum) {
            consultEndArray.push(currentTime + b);
            consultEndArray.sort((x, y) => y - x); // 상담종료시각을 담은 배열을 정렬해 pop을 사용할 수 있게 함
            index += 1;
        }
      // 상담시간이 되었지만, 멘토가 모두 상담을 하고 있어 기다려야 하는 상황에는 대기시간을 더해줌
        else if (currentTime >= a) {
          // 기다리고 있는 사람수 확인
            let waitUser = 0;
            for (let i = index; i < reqArray.length; i++) {
                if (currentTime >= reqArray[i][0]) waitUser++;
                else break;
            }
                
          // 기다리는 사람수만큼 대기시간을 더하고, 현재시간을 1분만큼 증가시킴
            waitTimeSum += waitUser;
            currentTime += 1;
        }
      
      // 시간을 1분 증가시킴
        else currentTime += 1;
    }
        
    return waitTimeSum;
}

멘토수를 분배하는 모든 경우의 수 구하기

  • 경우의 수가 많지 않기 때문에, 재귀함수를 사용해 멘토를 분배하는 모든 경우의 수를 구해주자.
  • 멘토수를 담은 배열이 항상 2차원을 유지할 수 있게 유의하자.
  • 코드의 구조는 아래와 같다.
    • 멘토 유형이 1개 남았을 경우, 즉 나머지 멘토를 전부 한 유형이 가져가야 할 경우, 재귀함수로 배열에 남은 멘토수를 마지막 원소로 가지게 한 2차원 배열을 반환한다.
    • 남은 유형 수와 멘토수가 같을 경우, 즉 남은 유형이 전부 멘토수가 1이 되는 경우, 재귀함수로 받은 배열에 남은 유형 수만큼 뒤에 1을 채운 2차원 배열을 반환한다.
    • 둘다 아닌 경우 현재 확인중인 유형의 상담원 수를 1부터 늘려가며 재귀함수를 사용해 모든 경우의 수를 탐색한다.
// 상담사 숫자, 현재 분배 상태를 담은 배열을 받아 멘토를 분배하는 모든 경우의 수를 찾는 함수
const getNumberSet = (divideLength, consultNum, currentArray) => {
  // 길이가 1이면 남은 상담원을 한 유형에 전부 집어넣음
    if (currentArray.length === divideLength - 1)
      return [[...currentArray, consultNum]];
  // 남은 사람수와 남은 유형수가 일치하면 남은 유형의 상담원수를 전부 1로 처리하여 반환
    else if (divideLength - currentArray.length === consultNum)
      return [[...currentArray, ...new Array(divideLength - currentArray.length).fill(1)]];
  // 둘다 아닌경우 현재 유형에 배정될 상담원 수를 1부터 가능한 최대치까지 배치한 모든 경우의 수 탐색
    else {
        const divideSet = [];
      // 해당 유형에서 가능한 상담원 수의 최대치는 현재 상담원 수 - 유형수 + 1
        for (let i = 1; i <= consultNum - (divideLength - currentArray.length) + 1; i++) 
          // 재귀함수를 통해 특정 상담원 수를 선택했을 때 모든 경우의 수를 가져오고, 각각을 반환할 배열에 push해줌
            getNumberSet(divideLength, consultNum - i, [...currentArray, i]).forEach(e => divideSet.push(e));
        
        return divideSet;
    }
}

대기시간의 최소값 찾기

  • 앞선 두 함수가 길었던 만큼 solution 함수의 길이는 짧아진다.
  • 앞서 제작한 두 함수를 사용해 각 유형, 멘토수 별로 대기시간을 담은 배열과, 멘토를 분배하는 경우의 수를 담은 배열을 제작해준다.
  • 멘토를 분배하는 경우의 수마다 대기시간의 합을 구해 최솟값을 찾아주면 답을 구할 수 있다.
function solution(k, n, reqs) {
    const timeArrayByType = []; // 유형, 멘토수 별로 대기시간을 담을 배열
  
  // timeArrayByType을 채울 로직
    for (let i = 1; i <= k; i++) {
      // reqs에서 각 타입에 맞는 유형만을 필터링함
        const currentReqs = reqs.filter(([a, b, c]) => c === i);
        
      // 멘토 숫자가 0인 경우는 존재하지 않음, 실수할 경우를 대비해 Infinity로 설정
        const timeArray = [Infinity];
      
      // 앞서 제작한 함수를 통해 현재 유형에서 멘토 수에 따른 대기시간을 구해 배열에 저장
        for(let j = 1; j <= n; j++) timeArray.push(getTime(currentReqs, j));
      
        timeArrayByType.push(timeArray);
    }
    
  // 멘토수를 분배하는 모든 경우의 수
    const combinationAll = getNumberSet(k, n, []);
  
  // 각 경우의수 별 대기시간의 합 구하기
    return combinationAll.map(data => {
        let waitTime = 0;
        for (let i = 0; i < data.length; i++) {
            waitTime += timeArrayByType[i][data[i]]
        }
        return waitTime;
    }).sort((a, b) => a - b)[0];
}

전체 코드 및 결과

// 각 유형별 상담 요청 배열과, 해당 유형의 상담원 수를 입력으로 받아 총 대기시간을 구하는 함수
const getTime = (reqArray, consultNum) => {    
    let currentTime = 0; // 현재 시간을 담는 변수
    let waitTimeSum = 0; // 총 대기시간을 담는 변수
    let index = 0; // 현재 대기중인 사람중 가장 먼저 상담을 받을 사람의 인덱스
    const consultEndArray = []; // 현재 상담을 받는 사람의 종료 시각을 담은 배열
        
  // 마지막 사람이 상담을 받기 시작한 순간 더이상의 대기는 발생하지 않게 됨
    while (index < reqArray.length) {
      // 상담이 종료된 순간 consultEndArray에서 해당 상담 종료시각값을 제거함
        while (consultEndArray.length > 0) {
            if (currentTime >= consultEndArray[consultEndArray.length - 1]) consultEndArray.pop();
            else break;
        }
            
      // 상담시작 시각과 상담 시간 가져오기
        const [a, b] = reqArray[index];

      // 상담시간이 되었고, 상담이 가능한 경우에는 상담 종료 시각을 consultEndArray에 넣고 인덱스를 1 올림
        if (currentTime >= a && consultEndArray.length < consultNum) {
            consultEndArray.push(currentTime + b);
            consultEndArray.sort((x, y) => y - x); // 상담종료시각을 담은 배열을 정렬해 pop을 사용할 수 있게 함
            index += 1;
        }
      // 상담시간이 되었지만, 멘토가 모두 상담을 하고 있어 기다려야 하는 상황에는 대기시간을 더해줌
        else if (currentTime >= a) {
          // 기다리고 있는 사람수 확인
            let waitUser = 0;
            for (let i = index; i < reqArray.length; i++) {
                if (currentTime >= reqArray[i][0]) waitUser++;
                else break;
            }
                
          // 기다리는 사람수만큼 대기시간을 더하고, 현재시간을 1분만큼 증가시킴
            waitTimeSum += waitUser;
            currentTime += 1;
        }
      
      // 시간을 1분 증가시킴
        else currentTime += 1;
    }
        
    return waitTimeSum;
}

// 상담사 숫자, 현재 분배 상태를 담은 배열을 받아 멘토를 분배하는 모든 경우의 수를 찾는 함수
const getNumberSet = (divideLength, consultNum, currentArray) => {
  // 길이가 1이면 남은 상담원을 한 유형에 전부 집어넣음
    if (currentArray.length === divideLength - 1) return [[...currentArray, consultNum]];
  // 남은 사람수와 남은 유형수가 일치하면 남은 유형의 상담원수를 전부 1로 처리하여 반환
    else if (divideLength - currentArray.length === consultNum) return [[...currentArray, ...new Array(divideLength - currentArray.length).fill(1)]];
  // 둘다 아닌경우 현재 유형에 배정될 상담원 수를 1부터 가능한 최대치까지 배치한 모든 경우의 수 탐색
    else {
        const divideSet = [];
      // 해당 유형에서 가능한 상담원 수의 최대치는 현재 상담원 수 - 유형수 + 1
        for (let i = 1; i <= consultNum - (divideLength - currentArray.length) + 1; i++) 
            getNumberSet(divideLength, consultNum - i, [...currentArray, i]).forEach(e => divideSet.push(e));
        
        return divideSet;
    }
}

function solution(k, n, reqs) {
    const timeArrayByType = []; // 유형, 멘토수 별로 대기시간을 담을 배열
  
  // timeArrayByType을 채울 로직
    for (let i = 1; i <= k; i++) {
      // reqs에서 각 타입에 맞는 유형만을 필터링함
        const currentReqs = reqs.filter(([a, b, c]) => c === i);
        
      // 멘토 숫자가 0인 경우는 존재하지 않음, 실수할 경우를 대비해 Infinity로 설정
        const timeArray = [Infinity];
      
      // 앞서 제작한 함수를 통해 현재 유형에서 멘토 수에 따른 대기시간을 구해 배열에 저장
        for(let j = 1; j <= n; j++) timeArray.push(getTime(currentReqs, j));
      
        timeArrayByType.push(timeArray);
    }
    
  // 멘토수를 분배하는 모든 경우의 수
    const combinationAll = getNumberSet(k, n, []);
  
  // 각 경우의수 별 대기시간의 합 구하기
    return combinationAll.map(data => {
        let waitTime = 0;
        for (let i = 0; i < data.length; i++) {
            waitTime += timeArrayByType[i][data[i]]
        }
        return waitTime;
    }).sort((a, b) => a - b)[0];
}

  • 경우의 수가 많지 않았던 만큼 완전탐색을 진행했음에도 불구하고 시간을 많이 소비하지 않았다.

출처:
https://school.programmers.co.kr/learn/courses/30/lessons/214288?language=javascript#

profile
SnowCat
냐아아아아아아아아앙
이전 포스트

Prefix Sum[Algorighm]

다음 포스트

[Algorightm] PCCP 기출문제 모음

0개의 댓글