반응형
SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)
2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,
A형 1문제 + B형 문제 1문제가 출제됩니다.
참고
- B형 필수 : 우선순위 큐 Priority Queue
https://www.codetree.ai/training-field/frequent-problems/problems/codetree-judger
문제를 요약하면 다음과 같다.
코드트리 채점기 준비
- 초기화 및 최초 task 추가
채점 요청
- t초에 우선순위 p인 url을 채점 대기 큐에 넣는다.
p가 작을수록, t가 작을수록 우선순위가 높다. (우선순위 큐 구현)
채점 대기 큐에 task 중 정확히 일치하는 url이 있다면 요청을 무시한다. (unordered_map으로 확인)
채점 시도
- 채점 대기 큐에서 채점이 가능한 task를 골라 채점을 진행한다.
task가 채점이 될 수 없는 조건에 의해 우선순위 큐가 하나라면 매우 비효율적으로 task를 찾게 된다.
따라서, domain 별로 우선순위 큐를 구현해야 한다
가장 최근에 진행된 채점 시작 시간 및 종료 시간, gap을 관리(= history)해야 한다.
쉬고 있는 채점기 중 번호가 작은 채점기를 찾기 위해 우선순위 큐로 구현해야 한다.
채점 종료
- j_id에 해당하는 채점기를 종료한다. (채점기 갱신, history 갱신)
채점기의 상태를 관리해야 한다.
채점 대기 큐 조회
- domain 별 우선순위 큐의 전체 합을 구한다.
매번 합을 구하지 않고, domain 별 우선순위 큐에 push / pop을 할 때마다 전체 count를 증가하거나 감소한다.
자료구조 및 메서드 정의
필요한 define을 정의한다. (INF = 최악의 우선순위 값)
#define MAX_D (300 + 10) // DOMAIN
#define MAX_J (50000 + 50) // Judge ID
#define INF (0x7fff0000)
#define READY (100)
#define REQUEST (200)
#define ATTEMPT (300)
#define CLOSED (400)
#define RETRIEVE (500)
URL이 주어질 때, domain과 문제 번호를 분리하기 위한 구조체와 함수를 만든다.
typedef struct st1
{
string domain;
int num;
}PROBLEM;
PROBLEM getProblem(string str)
{
PROBLEM ret;
string domain, numStr;
int len;
domain = numStr = "";
len = str.length();
int i;
for (i = 0; i < len; i++)
{
if (str[i] == '/') break;
domain += str[i];
}
i++;
for (; i < len; i++) numStr += str[i];
ret.domain = domain;
ret.num = stoi(numStr);
return ret;
}
'/' 에서 break를 한 후, substr로 domain과 num을 나눌 수도 있다.
ret.domain = str.substr(0, i);
ret.num = stoi(str.substr(i + 1));
URL을 domain / num으로 분리하면 URL_INFO에 순서대로 정보를 저장하게 된다.
domain 별 우선순위 큐에는 해당 domain의 URL 정보를 모두 가지고 있지 않고, ID만 추가해서 관리한다.
typedef struct st2
{
string url;
string domain;
int num;
}URL_INFO;
URL_INFO urlInfo[MAX_J]; // 입력된 URL 순서대로 정보 저장
int urlCounter;
/* ------------------------------------------------------------ */
j_id가 채점 중인지 확인하기 위해 다음과 같이 구조체를 선언한다.
status가 1이면 채점 중인 상태이고, 어떤 도메인이 채점 중인지는 domain에서 알 수 있다.
typedef struct st2
{
string domain;
int status;
}STATE_INFO;
STATE_INFO judgingInfo[MAX_J]; // j_id로 접근
최신 이력은 다음 구조체에서 관리한다.
가장 나중에 종료된 task를 domain 별로 관리한다.
typedef struct st4
{
int start;
int end;
}HISTORY;
HISTORY history[MAX_D];
모든 domain 별 우선순위 큐에 URL이 있는지 확인하는 unordered_map을 선언한다.
unordered_map<string, int> waitURLCheck;
우선순위 큐는 다음과 같이 구현한다.
typedef struct st5
{
int value; // 번호가 작은 채점기 id 또는 우선순위 p
int timeStamp;
int urlId;
}TASK;
TASK judgePQ[MAX_J];
int jhn;
TASK waitPQ[MAX_D][MAX_J];
int whn[MAX_D];
int totalWhn; // waitPQ의 전체 값
int isMin(TASK a, TASK b)
{
if (a.value != b.value) return a.value < b.value;
return a.timeStamp < b.timeStamp;
}
TASK pop(TASK* heap, int& hn)
{
TASK ret, tmp;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].value = INF;
heap[hn--].timeStamp = INF;
for (int i = 1; i * 2 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
i = i * 2 + 1;
}
}
return ret;
}
void push(TASK* heap, int& hn, TASK x)
{
TASK tmp;
heap[++hn] = x;
for (int i = hn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) return;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
}
}
각 도메인에 해당하는 우선순위 큐를 찾기 위해 unordered_map을 이용한다.
새로 들어오는 domain이라면 index가 증가하게 된다.
unordered_map<string, int> domainIndexMap;
int domainCounter;
int getDomainHeapIndex(string domain)
{
return domainIndexMap[domain];
}
void setDomainHeapIndex(string domain)
{
if (domainIndexMap.count(domain) != 0) return;
domainIndexMap[domain] = domainCounter++;
}코드트리 채점기 준비
입력 및 선언한 자료구조를 초기화한다.
int N;
char str[300];
string U0;
scanf("%d %s", &N, str);
// waitPQ 초기화
for (int i = 0; i < 300; i++) whn[i] = 0;
waitURLCheck.clear();
totalWhn = 0;
// 채점기 초기화
jhn = 0;
for (int n = 1; n <= N; n++)
{
TASK h = { 0 };
h.value = n; // j_id;
push(judgePQ, jhn, h);
}
for (int n = 1; n <= N; n++) judgingInfo[n].status = 0;
// 도메인 관련 정보 초기화
for (int i = 0; i < 300; i++) history[i].end = 0;
domainCounter = urlCounter = 0;
domainIndexMap.clear();
// U0 채점 대기 큐 추가
U0 = string(str);
waitURLCheck[U0] = 1;
PROBLEM p = getProblem(U0);
setDomainHeapIndex(p.domain);
task를 만들어서 해당되는 우선순위 큐에 추가한다.
그리고 전체 task 값도 증가한다.
url 정보(string)는 우선순위 큐에 모두 넣어서 이동하면 메모리 초과 및 성능 저하가 발생한다.
따라서 url에 mapping되는 index만 task에 추가하였다.
// task 선언
TASK task = { 0 };
task.timeStamp = 0;
task.value = 1;
task.urlId = urlCounter;
urlInfo[urlCounter].url = U0;
urlInfo[urlCounter].domain = p.domain;
urlInfo[urlCounter].num = p.num;
urlCounter++;
// 해당되는 도메인의 PQ에 task 추가
int domainHeapIndex = getDomainHeapIndex(p.domain);
push(waitPQ[domainHeapIndex], whn[domainHeapIndex], task);
totalWhn++;
전체 input은 다음과 같다.
void input()
{
int N;
char str[300];
string U0;
scanf("%d %s", &N, str);
// waitPQ 초기화
for (int i = 0; i < 300; i++) whn[i] = 0;
waitURLCheck.clear();
totalWhn = 0;
// 채점기 초기화
jhn = 0;
for (int n = 1; n <= N; n++)
{
TASK h = { 0 };
h.value = n; // j_id;
push(judgePQ, jhn, h);
}
for (int n = 1; n <= N; n++) judgingInfo[n].status = 0;
// 도메인 초기화
for (int i = 0; i < 300; i++) history[i].end = INF;
domainCounter = urlCounter = 0;
domainIndexMap.clear();
// U0 채점 대기 큐 추가
U0 = string(str);
waitURLCheck[U0] = 1;
PROBLEM p = getProblem(U0);
setDomainHeapIndex(p.domain);
// task 선언
TASK task = { 0 };
task.timeStamp = 0;
task.value = 1;
task.urlId = urlCounter;
urlInfo[urlCounter].url = U0;
urlInfo[urlCounter].domain = p.domain;
urlInfo[urlCounter++].num = p.num;
// 해당되는 도메인의 PQ에 task 추가
int domainHeapIndex = getDomainHeapIndex(p.domain);
push(waitPQ[domainHeapIndex], whn[domainHeapIndex], task);
totalWhn++;
}채점 요청
입력 받은 URL에 대해 채점 대기 큐에 정확히 일치하는 URL이 있다면 요청을 무시한다.
void request(int t, int p, char str[])
{
string u = string(str);
// 채점 대기 큐에 u와 일치하는 URL이 있는 경우
if (waitURLCheck[u] == 1) return;
...
그렇지 않은 경우, waitURLCheck에 해당 URL이 존재한다고 표시한다.
waitURLCheck[u] = 1;
그리고 해당 되는 URL을 input에서 task를 추가한 것처럼 domain 별 우선순위 큐에 넣는다.
PROBLEM problem = getProblem(u);
setDomainHeapIndex(problem.domain);
// task 선언
TASK task = { 0 };
task.timeStamp = t;
task.value = p;
task.urlId = urlCounter;
urlInfo[urlCounter].url = u;
urlInfo[urlCounter].domain = problem.domain;
urlInfo[urlCounter++].num = problem.num;
// 해당되는 도메인의 PQ에 task 추가
int domainHeapIndex = getDomainHeapIndex(problem.domain);
push(waitPQ[domainHeapIndex], whn[domainHeapIndex], task);
totalWhn++;
채점 시도
쉬고 있는 채점기가 없는 경우, 명령을 무시한다.
채점 가능한 task가 있다면, 쉬고 있는 채점기 중 가장 번호가 작은 채점기를 선택하고,
채점 상태(judingInfo)와 채점 대기 큐(waitURLCheck)를 갱신한다.
void attempt(int t)
{
// 쉬고 있는 채점기가 없는 경우
if (jhn == 0) return;
// 가능한 task 선택
TASK task = getPossibleTask(t);
if (task.value == INF) return;
URL_INFO info = urlInfo[task.urlId];
// 가능한 채점기 중 가장 번호가 작은 채점기 선택
TASK judge = pop(judgePQ, jhn);
int j_id = judge.value;
// 채점 상태 갱신
judgingInfo[j_id].domain = info.domain;
judgingInfo[j_id].status = 1;
// 채점 대기 큐 갱신
waitURLCheck[info.url] = 0;
}
채점 가능한 task는 도메인 별 우선순위 큐에서 가장 우선순위가 높은 task(waitPQ[i][1])만 체크하면 된다.
각 도메인에서 가장 우선순위가 높은 것이 채점 대상이 아니면, 해당 되는 도메인은 모두 채점 대상이 아니다.
이 도메인 중 채점 중이거나 gap 조건이 맞지 않는 경우는 고려되지 않는다.
TASK getPossibleTask(int currentTime)
{
TASK ret = { 0 };
ret.timeStamp = INF;
ret.value = INF;
int index = -1;
for (int i = 0; i < domainCounter; i++)
{
// end가 INF인 경우, 채점 중이라고 판단
if (history[i].end > currentTime) continue;
// 채점 대기 큐에 아무 것도 없는 경우
if (whn[i] == 0) continue;
TASK task = waitPQ[i][1];
if (isMin(task, ret))
{
index = i;
ret = task;
}
}
// 가능한 작업이 있는 경우
if (index != -1)
{
pop(waitPQ[index], whn[index]);
history[index].start = currentTime;
history[index].end = INF;
totalWhn--;
}
return ret;
}
위의 코드에서 하단의 "가능한 작업이 있는 경우"를 먼저 살펴보자.
도메인 중 가장 우선순위가 높은 task를 pop하고, 해당되는 history의 start가 갱신된다.
그리고 이 작업은 채점 중 상태로 변하게 되므로 end를 가장 큰 값(INF)으로 표시해둔다.
이러면 if (history[i].end > currentTime) continue; 에서 채점 중인 경우도 포함해서 작업을 분류할 수 있다.
pop을 했기 때문에 전체 우선순위 큐의 크기를 감소(totalWhn--)한다.
// 가능한 작업이 있는 경우
if (index != -1)
{
pop(waitPQ[index], whn[index]);
history[index].start = currentTime;
history[index].end = INF;
totalWhn--;
}
따라서 채점 중이거나 gap 조건에 맞지 않는 도메인은 무시하게 된다. (gap 조건은 채점 종료에서 end를 처리)
for (int i = 0; i < domainCounter; i++)
{
// end가 INF인 경우, 채점 중이라고 판단
if (history[i].end > currentTime) continue;
// 채점 대기 큐에 아무 것도 없는 경우
if (whn[i] == 0) continue;
TASK task = waitPQ[i][1];
if (isMin(task, ret))
{
index = i;
ret = task;
}
}채점 종료
judgingInfo를 참고하여 채점 중인 경우, 채점을 종료한다.
채점기의 상태를 종료로 변경하고, 종료된 채점기를 다시 우선순위 큐에 추가한다.
judgingInfo에서 해당되는 도메인의 우선순위 큐를 찾아 history를 갱신한다.
이때, 문제에서 제시한 gap 조건을 end에 기록한다.
void closed(int t, int j_id)
{
// j_id 채점기가 진행하던 채점이 없는 경우
if (judgingInfo[j_id].status == 0) return;
// 채점 종료
STATE_INFO info = judgingInfo[j_id];
int domainIndex = getDomainHeapIndex(info.domain);
// 쉬는 상태로 변경
judgingInfo[j_id].status = 0;
// 종료된 채점기를 다시 heap에 추가
TASK judge = { 0 };
judge.value = j_id;
push(judgePQ, jhn, judge);
// History 갱신
int gap = t - history[domainIndex].start;
history[domainIndex].end = history[domainIndex].start + 3 * gap;
}채점 대기 큐 조회
전체 우선순위 큐의 크기를 출력한다.
void retrieve(int t)
{
printf("%d\n", totalWhn);
}전체 코드는 다음과 같다.
#include <stdio.h>
#include <string>
#include <unordered_map>
using namespace std;
#define MAX_D (300 + 10) // DOMAIN
#define MAX_J (50000 + 50) // Judge ID
#define INF (0x7fff0000)
#define READY (100)
#define REQUEST (200)
#define ATTEMPT (300)
#define CLOSED (400)
#define RETRIEVE (500)
/* ------------------------------------------------------------ */
// URL → domain / 문제 번호 분리
typedef struct st1
{
string domain;
int num;
}PROBLEM;
PROBLEM getProblem(string str)
{
PROBLEM ret;
string domain, numStr;
int len;
domain = numStr = "";
len = str.length();
int i;
for (i = 0; i < len; i++)
{
if (str[i] == '/') break;
domain += str[i];
}
i++;
for (; i < len; i++) numStr += str[i];
ret.domain = domain;
ret.num = stoi(numStr);
return ret;
}
/* ------------------------------------------------------------ */
// URL에서 domain을 분리하여 저장
// 우선순위 큐에는 ID를 저장하고, 해당 ID로 url 정보에 접근 (우선순위 큐 메모리 절약)
typedef struct st2
{
string url;
string domain;
int num;
}URL_INFO;
URL_INFO urlInfo[MAX_J]; // 입력된 URL 순서대로 정보 저장
int urlCounter;
/* ------------------------------------------------------------ */
// j_id 채점기가 채점 중인지 확인하기 위한 자료구조
typedef struct st3
{
string domain;
int status;
}STATE_INFO;
STATE_INFO judgingInfo[MAX_J]; // j_id로 접근
/* ------------------------------------------------------------ */
// 도메인에 대한 최신 채점 이력
typedef struct st4
{
int start;
int end;
}HISTORY;
HISTORY history[MAX_D];
/* ------------------------------------------------------------ */
// 우선순위 큐
// 전체 우선순위 큐에 URL이 있는지 확인하는 unorderd_map
unordered_map<string, int> waitURLCheck;
typedef struct st5
{
int value; // 번호가 작은 채점기 id 또는 우선순위 p
int timeStamp;
int urlId;
}TASK;
TASK judgePQ[MAX_J];
int jhn;
TASK waitPQ[MAX_D][MAX_J];
int whn[MAX_D];
int totalWhn; // waitPQ의 전체 값
int isMin(TASK a, TASK b)
{
if (a.value != b.value) return a.value < b.value;
return a.timeStamp < b.timeStamp;
}
TASK pop(TASK* heap, int& hn)
{
TASK ret, tmp;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].value = INF;
heap[hn--].timeStamp = INF;
for (int i = 1; i * 2 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
i = i * 2 + 1;
}
}
return ret;
}
void push(TASK* heap, int& hn, TASK x)
{
TASK tmp;
heap[++hn] = x;
for (int i = hn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) return;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
}
}
/* ------------------------------------------------------------ */
// 도메인에 해당하는 heap을 찾기 위한 unordered_map
unordered_map<string, int> domainIndexMap;
int domainCounter;
int getDomainHeapIndex(string domain)
{
return domainIndexMap[domain];
}
void setDomainHeapIndex(string domain)
{
if (domainIndexMap.count(domain) != 0) return;
domainIndexMap[domain] = domainCounter++;
}
/* ------------------------------------------------------------ */
void printTask(TASK t)
{
printf("value : %d / time: %d / %s \n", t.value, t.timeStamp, urlInfo[t.urlId].url.c_str());
}
void printQueue(int index)
{
printf("==========================\nprintQueue %d\n", index);
for (int i = 1; i <= whn[index]; i++)
printTask(waitPQ[index][i]);
printf("==============================\n\n");
}
void input()
{
int N;
char str[300];
string U0;
scanf("%d %s", &N, str);
// waitPQ 초기화
for (int i = 0; i < 300; i++) whn[i] = 0;
waitURLCheck.clear();
totalWhn = 0;
// 채점기 초기화
jhn = 0;
for (int n = 1; n <= N; n++)
{
TASK h = { 0 };
h.value = n; // j_id;
push(judgePQ, jhn, h);
}
for (int n = 1; n <= N; n++) judgingInfo[n].status = 0;
// 도메인 관련 정보 초기화
for (int i = 0; i < 300; i++) history[i].end = 0;
domainCounter = urlCounter = 0;
domainIndexMap.clear();
// U0 채점 대기 큐 추가
U0 = string(str);
waitURLCheck[U0] = 1;
PROBLEM p = getProblem(U0);
setDomainHeapIndex(p.domain);
// task 선언
TASK task = { 0 };
task.timeStamp = 0;
task.value = 1;
task.urlId = urlCounter;
urlInfo[urlCounter].url = U0;
urlInfo[urlCounter].domain = p.domain;
urlInfo[urlCounter++].num = p.num;
// 해당되는 도메인의 PQ에 task 추가
int domainHeapIndex = getDomainHeapIndex(p.domain);
push(waitPQ[domainHeapIndex], whn[domainHeapIndex], task);
totalWhn++;
}
void request(int t, int p, char str[])
{
string u = string(str);
// 채점 대기 큐에 u와 일치하는 URL이 있는 경우
if (waitURLCheck[u] == 1) return;
waitURLCheck[u] = 1;
PROBLEM problem = getProblem(u);
setDomainHeapIndex(problem.domain);
// task 선언
TASK task = { 0 };
task.timeStamp = t;
task.value = p;
task.urlId = urlCounter;
urlInfo[urlCounter].url = u;
urlInfo[urlCounter].domain = problem.domain;
urlInfo[urlCounter++].num = problem.num;
// 해당되는 도메인의 PQ에 task 추가
int domainHeapIndex = getDomainHeapIndex(problem.domain);
push(waitPQ[domainHeapIndex], whn[domainHeapIndex], task);
totalWhn++;
}
TASK getPossibleTask(int currentTime)
{
TASK ret = { 0 };
ret.timeStamp = INF;
ret.value = INF;
int index = -1;
for (int i = 0; i < domainCounter; i++)
{
// end가 INF인 경우, 채점 중이라고 판단
if (history[i].end > currentTime) continue;
// 채점 대기 큐에 아무 것도 없는 경우
if (whn[i] == 0) continue;
TASK task = waitPQ[i][1];
if (isMin(task, ret))
{
index = i;
ret = task;
}
}
// 가능한 작업이 있는 경우
if (index != -1)
{
pop(waitPQ[index], whn[index]);
history[index].start = currentTime;
history[index].end = INF;
totalWhn--;
}
return ret;
}
void attempt(int t)
{
// 쉬고 있는 채점기가 없는 경우
if (jhn == 0) return;
// 가능한 task 선택
TASK task = getPossibleTask(t);
if (task.value == INF) return;
URL_INFO info = urlInfo[task.urlId];
// 가능한 채점기 중 가장 번호가 작은 채점기 선택
TASK judge = pop(judgePQ, jhn);
int j_id = judge.value;
// 채점 상태 갱신
judgingInfo[j_id].domain = info.domain;
judgingInfo[j_id].status = 1;
// 채점 대기 큐 갱신
waitURLCheck[info.url] = 0;
}
void closed(int t, int j_id)
{
// j_id 채점기가 진행하던 채점이 없는 경우
if (judgingInfo[j_id].status == 0) return;
// 채점 종료
STATE_INFO info = judgingInfo[j_id];
int domainIndex = getDomainHeapIndex(info.domain);
// 쉬는 상태로 변경
judgingInfo[j_id].status = 0;
// 종료된 채점기를 다시 heap에 추가
TASK judge = { 0 };
judge.value = j_id;
push(judgePQ, jhn, judge);
// History 갱신
int gap = t - history[domainIndex].start;
history[domainIndex].end = history[domainIndex].start + 3 * gap;
}
void retrieve(int t)
{
printf("%d\n", totalWhn);
}
int main()
{
int Q;
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
{
int COMMAND;
scanf("%d", &COMMAND);
if (COMMAND == READY) input();
else if (COMMAND == REQUEST)
{
int t, p;
char str[300];
scanf("%d %d %s", &t, &p, str);
request(t, p, str);
}
else if (COMMAND == ATTEMPT)
{
int t;
scanf("%d", &t);
attempt(t);
}
else if (COMMAND == CLOSED)
{
int t, j_id;
scanf("%d %d", &t, &j_id);
closed(t, j_id);
}
else if (COMMAND == RETRIEVE)
{
int t;
scanf("%d", &t);
retrieve(t);
}
}
return 0;
}반응형
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| [코드트리] 코드트리 메신저 (삼성 SW 역량테스트 2023 하반기 오전 2번, B형) (0) | 2024.08.08 |
|---|---|
| [코드트리] 왕실의 기사 대결 (삼성 SW 역량테스트 2023 하반기 오전 1번) (0) | 2024.08.04 |
| [코드트리] 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번) (0) | 2024.07.31 |
| [코드트리] 토끼와 경주 (삼성 SW 역량테스트 2023 상반기 오전 2번, B형) (0) | 2024.07.28 |
| [코드트리] 포탑 부수기 (삼성 SW 역량테스트 2023 상반기 오전 1번) (0) | 2024.07.28 |
댓글