[프로그래머스 Lv.2] 서버 증설 횟수

https://school.programmers.co.kr/learn/courses/30/lessons/389479

프로그래머스

 

처음 푼 방법

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> players, int m, int k) {
    int answer = 0;
    
    // 현재 서버
    int curServer = 0;
    // 반납시간
    int finServer = -1;
    
    for(int i = 0; i < players.size(); i++) {
        cout << "[" << i << "]" << "before: curServer, finServer, answer -> " << curServer << ", " << finServer << "," << answer << "\n";

        if (i >= finServer) {
            curServer = 0;
        }
        
        int cnt = players[i] / m;
        
        if (cnt > curServer) {
            answer += (cnt - curServer);
            curServer = cnt;
            finServer = i + k;
        }
        cout << "[" << i << "]" << "after: curServer, finServer, answer -> " << curServer << ", " << finServer << "," << answer << "\n";
    }
    
    return answer;
}

 

이 방법에선 문제가 있다.

[16]before: curServer, finServer, answer -> 2, 18,3
[16]after: curServer, finServer, answer -> 2, 18,3
[17]before: curServer, finServer, answer -> 2, 18,3
[17]after: curServer, finServer, answer -> 4, 22,5

 

여기서 문제를 찾을 수 있었는데

이전에 증설된 서버의 반납시간이 있음에도 불구하고, 새로 생기면 반납시간(finServer)을 덮어쓰는 형태가 된다.

• 따라서 이전에 만든 서버가 반납시간이 되었음에도 불구하고 반납되지 못하고 계속해서 증설만 되는 형태가 되었다.

따라서 반납시간, 증설된 서버를 함께 저장하는 pair<int, int> 형태로 저장하도록 수정했다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<int> players, int m, int k) {
    int answer = 0;
    
    // 현재 서버
    int curServer = 0;
    // 반납시간 정보를 저장하는 큐 (반납시간, 서버수)
    queue<pair<int, int>> finServer;
    
    for(int i = 0; i < players.size(); i++) {
        cout << "[" << i << "]" << "before: curServer, answer -> " << curServer << ", " << answer << "\n";

        // 반납 시간이 된 서버들 처리
        while (!finServer.empty() && finServer.front().first <= i) {
            curServer -= finServer.front().second;
            finServer.pop();
        }
        
        int cnt = players[i] / m;
        
        if (cnt > curServer) {
            int newServer = cnt - curServer;
            answer += newServer;
            curServer += newServer;
            finServer.push(make_pair(i + k, newServer));  // (반납시간, +된 서버수) 저장
        }
        cout << "[" << i << "]" << "after: curServer, answer -> " << curServer << ", " << answer << "\n";
    }
    
    return answer;
}

 

for문을 돌면서 특정 플레이 타임이 되었을 때 while문으로 queue를 돌면서 반납시간이 된 서버들을 pop 시켜주는 형태로 바꿨다.