[코드트리] 코드트리 오마카세 (삼성 SW 역량테스트 2023 하반기 오후 2번, B형)

삼성 A형 전체 링크

삼성 B형 전체 링크

 

2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,

A형 1문제 + B형 문제 1문제가 출제됩니다.

 

참고

- B형 필수 : 우선순위 큐 Priority Queue

- BOJ 10825 : 국영수

 

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-omakase

이후 설명 및 입/출력은 링크 참고

 

벨트의 길이와 주어진 시간이 1,000,000,000으로 매우 크기 때문에 매번 초밥을 옮기면 시간초과가 나게 된다.

하지만, 손님이 앉은 시간과 위치, 초밥이 생성된 시간과 위치로 손님이 초밥을 먹는 시간을 구할 수 있다.

 

초밥을 먹는 손님이 앉은 다음에, 초밥이 생성된 경우를 먼저 고려해 보자.

 

손님의 위치보다 초밥이 생성된 위치가 더 앞에 있다면, 

초밥은 벨트의 끝(L)으로 이동한 뒤, 다시 벨트의 처음에서 손님의 위치까지 이동해야 한다.

즉, L - 초밥 생성 위치 + 손님의 위치만큼 시간이 걸린다.

 

초밥이 생성된 위치가 손님의 위치보다 뒤라면,

손님의 위치에서 초밥의 위치를 뺀 만큼 시간이 걸린다.

 

코드로 표현하면 다음과 같다.

	// 손님이 앉은 후, 초밥이 생성된 경우
	if (guestTime < sushiTime)
	{
		if (guestPos < sushiPos) // 초밥이 더 앞에 있는 경우		
			timeDiff = L - sushiPos + guestPos;		
		else		
			timeDiff = guestPos - sushiPos;		

		return sushiTime + timeDiff;
	}

 

이제 초밥이 생성된 후, 손님이 앉은 경우를 고려해보자.

 

이 경우, 초밥이 생성된 위치에서 손님이 앉았을 때 시간을 고려해 변경된 위치를 찾아야 한다.

	// 손님이 앉은 시점에서 초밥의 위치
	int sushiGuestPos = (sushiPos + (guestTime - sushiTime)) % L;

 

이 위치가 손님의 앞이냐 뒤냐에 따라 위의 방식대로 초밥이 사라지는 시간을 구할 수 있다.

	else // 초밥이 생성된 후 손님이 앉은 경우
	{
		// 손님이 앉은 시점에서 초밥의 위치
		int sushiGuestPos = (sushiPos + (guestTime - sushiTime)) % L;
		int timeDiff;

		if (guestPos < sushiGuestPos)
			timeDiff = L - sushiGuestPos + guestPos;
		else
			timeDiff = guestPos - sushiGuestPos;

		return guestTime + timeDiff;
	}

 

초밥이 사라지는 시간을 구하는 함수는 다음과 같다.

int getEatingTime(GUEST_INFO& oi, SUSHI& sushi)
{
	int guestTime = oi.timeStamp;
	int guestPos = oi.position;
	int sushiTime = sushi.timeStamp;
	int sushiPos = sushi.position;
	int timeDiff = 0;

	// 손님이 앉은 후, 초밥이 생성된 경우
	if (guestTime < sushiTime)
	{
		if (guestPos < sushiPos) // 초밥이 더 앞에 있는 경우		
			timeDiff = L - sushiPos + guestPos;		
		else		
			timeDiff = guestPos - sushiPos;		

		return sushiTime + timeDiff;
	}
	else // 초밥이 생성된 후 손님이 앉은 경우
	{
		// 손님이 앉은 시점에서 초밥의 위치
		int sushiGuestPos = (sushiPos + (guestTime - sushiTime)) % L;
		int timeDiff;

		if (guestPos < sushiGuestPos)
			timeDiff = L - sushiGuestPos + guestPos;
		else
			timeDiff = guestPos - sushiGuestPos;

		return guestTime + timeDiff;
	}
}

 

초밥이 사라지는 시간을 구할 수 있으므로, 나머지는 다음과 같이 구현하면 된다.

 

1) 주방장의 초밥 만들기

- 초밥을 먹는 손님의 index를 unordered_map으로 관리한다.

- 손님이 입장하지 않은 경우, 배열에 초밥을 추가한다.

- 손님이 입장한 경우, 우선순위 큐에 초밥을 추가한다.

- 전체 초밥 수를 증가한다.

 

2) 손님 입장

- 초밥을 먹는 손님의 index를 unordered_map으로 관리한다.

- 손님이 입장하였으므로, 손님의 정보를 기록한다.

- 배열에 있는 초밥을 우선순위 큐에 추가한다.

- 전체 손님 수를 증가한다.

 

3) 사진 촬영

- 사진 촬영 시간을 기준으로 초밥이 사라지는지 확인한다.

- 우선순위 큐에서 사진 촬영 시간보다 작은 경우 모두 pop한다.

- pop 된 정보를 바탕으로 전체 초밥 수와 전체 손님 수를 갱신한다.

 

손님이 입장한 후부터 초밥이 사라지는 시간을 구할 수 있으므로,

손님이 입장하기 전에는 배열에 초밥을 넣고, 손님이 나타나면 우선순위 큐에 초밥을 넣는다.

 

우선순위 큐는 초밥이 사라지는 시간이 작을수록 우선순위가 높도록 한다.

그러면 사진 촬영 시점보다 사라지는 시간이 적은 초밥을 쉽게 제거할 수 있다.

 

구현한 우선순위 큐는 다음과 같다.

typedef struct st3
{
	int eatingTime;
	int guestIndex;
}HEAP;

HEAP heap[MAX_SUSHI];
int hn;

HEAP pop()
{
	int i;
	HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].eatingTime = INF;

	for (i = 1; i * 2 <= hn;)
	{
		if (heap[i].eatingTime < heap[i * 2].eatingTime && heap[i].eatingTime < heap[i * 2 + 1].eatingTime) break;
		if (heap[i * 2].eatingTime < heap[i * 2 + 1].eatingTime)
		{
			tmp = heap[i];
			heap[i] = heap[i * 2];
			heap[i * 2] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i];
			heap[i] = heap[i * 2 + 1];
			heap[i * 2 + 1] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP x)
{
	int i;
	HEAP tmp;
	heap[++hn] = x;

	for (i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].eatingTime < heap[i].eatingTime) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

---

주방장의 초밥 만들기

 

초밥 구조체는 다음과 같다.

구조체에 string이 있는 경우, 메모리가 커져 성능이 저하되므로, 손님의 index만 저장한다.

손님 입장 전 생성된 초밥은 vector로 관리한다.

typedef struct st1
{
	int timeStamp;
	int position;
	int guestIndex;
	int eatingTime;
}SUSHI;

vector<SUSHI> waiting[MAX_GUEST];
int totalSushi;

 

손님 구조체는 다음과 같다.

unordered_map과 oindex로 손님의 index를 관리한다.

손님의 정보는 GUEST_INFO 배열에 저장된다.

typedef struct st2
{
	int timeStamp;
	int position;
	int count;
	int enter;
}GUEST_INFO;

unordered_map<string, int> guestMap;
GUEST_INFO guestInfo[MAX_GUEST];
int oindex;
int totalGuest;

 

주방장의 초밥 만들기는 다음과 같다.

손님이 입장하지 않으면, 초밥이 언제 사라지는지 알 수 없으므로 eatingTime = INF가 된다.

void makeSushi(int t, int x, char name[])
{
	string guestName = string(name);

	if (guestMap.count(guestName) == 0)
		guestMap[guestName] = oindex++;

	int guestIndex = guestMap[guestName];

	SUSHI sushi = { t, x, guestIndex, INF };

	if(guestInfo[guestIndex].enter == 0)
		waiting[guestIndex].push_back(sushi);
	else
	{
		int eatingTime = getEatingTime(guestInfo[guestIndex], sushi);
		
		push({ eatingTime, guestIndex });
	}
		
	totalSushi++;
}

---

손님 입장

 

손님 입장은 다음과 같다.

enter에 1을 표시해서 손님이 입장했다는 표시를 하고,

waiting에 있는 초밥이 사라지는 시간을 구해서 우선순위 큐에 넣는다.

void enterGuest(int t, int x, char name[], int n)
{
	string guestName = string(name);

	if (guestMap.count(guestName) == 0)
		guestMap[guestName] = oindex++;

	int guestIndex = guestMap[guestName];

	guestInfo[guestIndex] = { t, x, n, 1 };

	totalGuest++;

	if (waiting[guestIndex].size() != 0)
	{
		for (auto sushi : waiting[guestIndex])
		{
			int eatingTime = getEatingTime(guestInfo[guestIndex], sushi);

			push({ eatingTime, guestIndex });
		}
	}
}

---

사진 촬영

 

우선순위 큐에는 사라지는 초밥의 시간이 적은 순서대로 들어있다.

주어진 촬영 시간 t 보다 초밥의 시간이 크다면 초밥은 제거되지 않으므로 종료한다.

그렇지 않은 경우, 초밥의 전체 개수와 해당 손님이 먹을 초밥의 수를 줄인다.

그리고 손님이 먹을 초밥의 수가 0이되면 전체 손님 수를 줄인다.

void photo(int t)
{
	while (hn)
	{
		HEAP h = heap[1];
		
		if (h.eatingTime > t) break;
		
		pop();

		totalSushi--;
		guestInfo[h.guestIndex].count--;

		if (guestInfo[h.guestIndex].count == 0) totalGuest--;
	}

	printf("%d %d\n", totalGuest, totalSushi);
}

 

---

전체 코드는 다음과 같다.

#include <stdio.h>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

#define MAX_SUSHI (100000 + 500)
#define MAX_GUEST (15000 + 500)

#define MAKE_SUSHI (100)
#define ENTER_GUEST (200)
#define PHOTO (300)
#define INF (0x7fff0000)

int L;

typedef struct st1
{
	int timeStamp;
	int position;
	int guestIndex;
	int eatingTime;
}SUSHI;

vector<SUSHI> waiting[MAX_GUEST];
int totalSushi;

typedef struct st2
{
	int timeStamp;
	int position;
	int count;
	int enter;
}GUEST_INFO;

unordered_map<string, int> guestMap;
GUEST_INFO guestInfo[MAX_GUEST];
int oindex;
int totalGuest;

typedef struct st3
{
	int eatingTime;
	int guestIndex;
}HEAP;

HEAP heap[MAX_SUSHI];
int hn;

HEAP pop()
{
	int i;
	HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].eatingTime = INF;

	for (i = 1; i * 2 <= hn;)
	{
		if (heap[i].eatingTime < heap[i * 2].eatingTime && heap[i].eatingTime < heap[i * 2 + 1].eatingTime) break;
		if (heap[i * 2].eatingTime < heap[i * 2 + 1].eatingTime)
		{
			tmp = heap[i];
			heap[i] = heap[i * 2];
			heap[i * 2] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i];
			heap[i] = heap[i * 2 + 1];
			heap[i * 2 + 1] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP x)
{
	int i;
	HEAP tmp;
	heap[++hn] = x;

	for (i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].eatingTime < heap[i].eatingTime) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int getEatingTime(GUEST_INFO& oi, SUSHI& sushi)
{
	int& guestTime = oi.timeStamp;
	int& guestPos = oi.position;
	int& sushiTime = sushi.timeStamp;
	int& sushiPos = sushi.position;
	int timeDiff = 0;

	// 손님이 앉은 후, 초밥이 생성된 경우
	if (guestTime < sushiTime)
	{
		if (guestPos < sushiPos) // 초밥이 더 앞에 있는 경우		
			timeDiff = L - sushiPos + guestPos;
		else
			timeDiff = guestPos - sushiPos;

		return sushiTime + timeDiff;
	}
	else // 초밥이 생성된 후 손님이 앉은 경우
	{
		// 손님이 앉은 시점에서 초밥의 위치
		int sushiGuestPos = (sushiPos + (guestTime - sushiTime)) % L;
		int timeDiff;

		if (guestPos < sushiGuestPos)
			timeDiff = L - sushiGuestPos + guestPos;
		else
			timeDiff = guestPos - sushiGuestPos;

		return guestTime + timeDiff;
	}
}

void makeSushi(int t, int x, char name[])
{
	string guestName = string(name);

	if (guestMap.count(guestName) == 0)
		guestMap[guestName] = oindex++;

	int guestIndex = guestMap[guestName];

	SUSHI sushi = { t, x, guestIndex, INF };

	if(guestInfo[guestIndex].enter == 0)
		waiting[guestIndex].push_back(sushi);
	else
	{
		int eatingTime = getEatingTime(guestInfo[guestIndex], sushi);

		push({ eatingTime, guestIndex });
	}
		
	totalSushi++;
}

void enterGuest(int t, int x, char name[], int n)
{
	string guestName = string(name);

	if (guestMap.count(guestName) == 0)
		guestMap[guestName] = oindex++;

	int guestIndex = guestMap[guestName];

	guestInfo[guestIndex] = { t, x, n, 1 };

	totalGuest++;

	if (waiting[guestIndex].size() != 0)
	{
		for (auto sushi : waiting[guestIndex])
		{
			int eatingTime = getEatingTime(guestInfo[guestIndex], sushi);

			push({ eatingTime, guestIndex });
		}
	}
}

void photo(int t)
{
	while (hn)
	{
		HEAP h = heap[1];
		
		if (h.eatingTime > t) break;
		
		pop();

		totalSushi--;
		guestInfo[h.guestIndex].count--;

		if (guestInfo[h.guestIndex].count == 0) totalGuest--;
	}

	printf("%d %d\n", totalGuest, totalSushi);
}

int main()
{
	int Q;

	scanf("%d %d", &L, &Q);

	for (int q = 0; q < Q; q++)
	{
		int COMMAND;

		scanf("%d", &COMMAND);

		if (COMMAND == MAKE_SUSHI)
		{
			int t, x;
			char name[30 + 5];
			scanf("%d %d %s", &t, &x, name);
			makeSushi(t, x, name);
		}
		else if (COMMAND == ENTER_GUEST)
		{
			int t, x, n;
			char name[30 + 5];
			scanf("%d %d %s %d", &t, &x, name, &n);
			enterGuest(t, x, name, n);
		}
		else if (COMMAND == PHOTO)
		{
			int t;
			scanf("%d", &t);
			photo(t);
		}
	}

	return 0;
}