https://school.programmers.co.kr/learn/courses/30/lessons/389479
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
처음 푼 방법
#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 시켜주는 형태로 바꿨다.

반응형
'PS' 카테고리의 다른 글
| [프로그래머스 Lv.2] 비밀 코드 해독 (0) | 2025.12.10 |
|---|---|
| [BOJ 1027] 고층 건물 (1) | 2025.12.09 |
| [프로그래머스 Lv.2] 완전범죄 (0) | 2025.12.08 |
| [BOJ 2179] 비슷한 단어 (0) | 2025.12.08 |
| [BOJ 14658] 하늘에서 별똥별이 빗발친다 (0) | 2025.12.08 |