[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 자료구조 - 멀티태스킹(카카오 먹방 문제 변형)

문제

현수의 컴퓨터는 멀티태스킹이 가능하다. 처리해야 할 작업이 N개 들어오면 현수의 컴퓨터는 작업을 1부터 N까지의 번호를 부여하고 처리를 다음과 같이 한다.
1) 컴퓨터는 1번 작업부터 순서대로 1초씩 작업을 한다. 즉 각 작업을 1초만 작업하고 다음 작업을 하는 식이다.
2) 마지막 번호의 작업을 1초 했으면 다시 1번 작업으로 가서 다시 1초씩 후속 처리를 한다.
3) 처리가 끝난 작업은 작업 스케쥴에서 사라지고 새로운 작업은 들어오지 않는다.
그런데 현수의 컴퓨터가 일을 시작한 지 K초 후에 정전이 되어 컴퓨터가 일시적으로 멈추었 다. 전기가 들어오고 나서 현수의 컴퓨터가 몇 번 작업부터 다시 시작해야 하는지 알아내는 프로그램을 작성하세요.

💡 입력설명
첫 번째 줄에 작업의 개수 N(1<=N<=2,000)이 주어지고 그 다음 N줄에 걸쳐 각 작업을 처리하는데 걸리는 시간이 초단위로 주어진다. 한 작업을 처리하는데 필요한 시간은 1,000를 넘지 않는다. 마지막 줄에 정전이 발생한 시간 K(1<=K<=2,000,000)가 주어진다.

💡 출력설명
첫 번째 줄에 몇 번 작업부터 다시 시작해야 하는지 작업 번호를 출력한다.
만약 더 이상 처리할 작업이 없다면 -1를 출력한다.

💡 입력예제
3
1
2
3
5

💡 출력예제
3

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,  i, ans, k, cnt = 0, pos = 0, tot = 0;
    scanf("%d", &n);
    vector<int> a(n + 1);
    // 작업을 처리하는데 걸리는 시간
    for(i = 1; i <= n; i++) {
        scanf("%d", &ans);
        a[i] = ans;
        tot += ans;
    }
    
    // 정전 발생한 시간
    scanf("%d", &k);
    
    // k값이 입력한 작업시간의 합보다 클 경우 -1출력 => k 도달하기도 전에 모두 0이다. 즉, 더이상 처리할 작업이 없다.
    if(k >= tot) {
        printf("-1");
        return 0;
    }
    
    while(1) {
        pos++;
        // pos가 작업의 개수를 넘었을 경우
        if(pos > n) {
            pos -= n;
        }
        
        // 0보다 클경우 1감소
        if(a[pos] > 0) {
            a[pos]--;
            cnt++;
        } else if(a[pos] == 0) {
            continue;
        }
        
        if(cnt == k) {
            break;
        }
    }
    
    
    while(1) {
        pos++;
        if(pos > n) {
            pos -= n;
        }
        if(a[pos] != 0) {
            break;
        }
    }
    printf("%d", pos);
    return 0;
}

 

---

설명

사용자로부터 작업의 개수 n을 입력받고 index가 1부터 시작하는 voector a를 선언한다.

작업 처리 시간을 입력받아 a에 할당하고 걸리는 시간의 총합을 tot에 할당해나간다.

처리할 작업이 없는 경우를 고려해야 하므로 정전 발생한 시간이 tot보다 크거나 같을 경우 -1을 출력한 후 return하여 해당 main함수를 종료한다.

그렇지 않을 경우 무한루프를 통해 pos를 1씩 증가해나간다. 해당 pos가 n보다 클 경우 vector의 크기를 초과한 것을 의미하므로 pos를 1로 할당하거나 현재 pos값에서 n을 뺀다.

현재 pos에 위치하는 a의 값이 0보다 클 경우 -1을하고 k값에 도달하는지를 판별하기 위해 동시에 cnt를 1씩 증가해나간다. 만약 값이 0일 경우 작업이 끝난 것을 의미하므로 다음 pos로 이동하기 위해 continue한다.

최종적으로 cnt가 k에 도달한 경우 정전이 발생한 시점이므로 break하여 해당 반복문을 빠져나온다.

마지막으로 정전 후 처리해야 할 작업 번호를 도출하기 위해 무한루프를 토해 pos를 1증가하고 해당 pos값이 0이 아닐 경우 break하여 반복문을 빠져나와 pos값을 출력한다.

 

---

배운 점

정전이 발생한 시점에서의 작업번호를 출력하여 문제를 해결하지 못하였다.
Simulation 알고리즘 구현에 대해서 이해하였지만 문제를 자세히 이해하는 것이 중요하다는 것을 알게되었다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.