백준 - 22234 가희와 은행

문제

https://www.acmicpc.net/problem/22234

22234번: 가희와 은행

1초마다 현재 처리하고 있는 고객의 id를 출력하는 문제였다.

손님들은 순서대로 줄을 서 있으며 한 번에 한 손님에게 할당할 수 있는 시간이 정해져있다. 할당된 시간이 끝나면 시간이 남은 손님일 경우에는 줄의 맨 뒤로 간다.

 

문제 풀이

queue를 이용해 풀 수 있었는데, 이때 queue에 넣는 순서가 중요하다.

 

영업 이후에 들어온 손님은 들어온 시간까지 알아야 하기 때문에 구조체를 사용했다.

영업 전에 들어온 손님 : 순서대로 queue에 넣기
영업 이후에 들어온 손님 : vector에 담아 언제 들어왔는지를 기준으로 정렬, 해당 시간에 queue에 삽입

 

이 문제는 1초마다 현재 처리중인 고객의 id를 출력해야 하는 문제여서 단순하게 for문으로 1초에 한 번씩 확인하면서 출력까지 해줬다. 현재 손님(nowCustomer)과 현재 손님의 남은 시간(nowCustomerTime)을 미리 정해놓고 현재 손님에게 할당중인 시간인 time을 0으로 초기화해준 후 for문을 시작했다.

 

for문 내부에서는 현재 시점이 다음 영업 이후에 오는 손님이 들어오는 시점이라면 queue에 삽입해줬다. 그리고 현재 손님의 업무를 처리했다. (출력, nowCustomerTime--)

 

업무 처리한 이후에 현재 손님의 업무가 모두 처리되었다면 다음 손님을 현재 손님으로 만들어줬다. 그리고 만약 현재 손님에게 할당된 시간을 다 썼는데 현재 손님의 업무가 남아있는 상태라면 현재 손님과 남은 시간을 다시 queue에 삽입해주고 다음 손님을 현재 손님으로 만들어줬다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

typedef struct info {
	int id;
	int t;
	int c;
}info;

bool compare(info a, info b) {
	return a.c < b.c;
}

int N, T, W, M; 

queue<pair<int, int>> q; //손님 id, 남은 시간

int main()
{
	//영업 전 들어온 손님 수, 한 번에 할당 가능한 시간, 출력 시간, 영업 후 들어온 손님 수
	scanf("%d %d %d", &N, &T, &W);

	int p, t, c; //손님 id, 일처리 걸리는 시간, 영업 시간 c초 후 들어옴

	//영업 전에 들어온 손님 -> queue에 순서대로 넣을 수 있음
	for (int i = 0; i < N; i++) { //0초일 때 대기큐의 앞에 있는 고객
		scanf("%d %d", &p, &t);
		q.push({ p,t });
	}

	scanf("%d", &M);
	//영업 후에 들어온 손님 -> list 저장 후 들어온 시간 순으로 정렬
	//시간에 맞게 순서대로 queue에 넣을 수 있음
	vector<info> customers(M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &p, &t, &c);
		customers[i].id = p;
		customers[i].t = t;
		customers[i].c = c;
	}

	sort(customers.begin(), customers.end(), compare);

	//1초 마다 출력
	int time = 0;
	int nowCustomer = q.front().first;
	int nowCustomerTime = q.front().second;
	q.pop();
	int j = 0;

	for (int i = 0; i < W; i++) {
		//영업 이후 들어온 손님 들여보내기
		if (j < customers.size() && customers[j].c-1 == i) {
			q.push({ customers[j].id, customers[j].t });
			j++;
		}

		printf("%d\n", nowCustomer);
		nowCustomerTime--;
		if (nowCustomerTime == 0) { //현재 손님 완료
			time = 0;
			if (q.empty()) continue;
			nowCustomer = q.front().first;
			nowCustomerTime = q.front().second;
			q.pop();
			continue;
		}
		time++;
		if (time == T) { //다음 손님으로 넘겨야 함
			q.push({ nowCustomer, nowCustomerTime });
			nowCustomer = q.front().first;
			nowCustomerTime = q.front().second;
			q.pop();
			time = 0;
		}
	}


	return 0;
}

/*
1 5 7
1 6
1
3 1 5

1 5 7
1 6
3
3 1 5
2 1 7
4 1 3
*/