[백준 BOJ] 26042번 식당 입구 대기 줄 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 큐를 활용한 기초 연산 문제

백준의 26042번 문제는 큐를 활용하여 간단하게 해결할 수 있는 자료구조 기초 문제이다.

해당 문제는 입력에 따라 학생이 식당에 들어오고 음식이 제공될 때 대기 학생의 최대 수와 그때의 대기줄 맨 뒤에 있는 학생의 번호를 구하여 출력해야 하는 문제이다.

이때 대기하는 학생이 최대인 경우가 중복되어 나타나는 경우에는 맨 뒤에 있는 학생의 번호는 가장 작은 경우를 출력하라고 문제에 명시되어 있다.

그리고 입력은 아래의 규칙대로 주어지니 참고하면 되겠다.

* 1 num :: num번 학생이 식당에 도착하여 대기를 시작함
* 2 :: (식당에 먼저 온 순서대로) 학생 1명에게 식사를 제공함

 

자료구조 큐는 선입선출 방식으로 원소를 처리하는데, 이러한 특성이 해당 문제와 걸맞다고 볼 수 있다.

따라서 큐의 작동 원리와 큐 내장 함수에 대한 이해가 있다면 쉽게 해결할 수 있을 것이다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력의 개수(n)를 입력받는다.

 

2) 대기하는 학생의 데이터를 처리할 큐를 미리 선언해 둔다.

그리고 최대 대기 학생 수를 저장할 변수 max를 0으로 초기화하여 선언한다.

또한, 대기 학생이 최대일 당시에 맨 뒤에 있는 학생 번호를 저장할 변수 cnt를 1000으로 초기화하여 선언한다.

(대기 학생이 최대일 경우가 중복될 수 있으며, 이 경우엔 학생의 번호가 최소인 경우를 출력하라고 명시되어 있다. 따라서, 필자는 임의의 큰 수로 초기값을 설정하였다.)

 

3) n의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- 명령어의 정보(com)를 입력받는다.

이때 com이 1이라면, 이는 학생 1명이 식당에 대기하기 시작했음을 의미한다. 따라서 이 경우엔, num을 추가로 입력받고 해당 num값을 q에 push 한다.

다만 com이 0이라면, 이는 학생이 식사를 받아 대기가 종료되었음을 의미한다. 따라서 이 경우엔, q에 대하여 pop 연산을 수행하도록 한다.

- com 명령어 처리가 완료되었다면, q.size()를 통해 현재 대기 중인 학생 수를 파악한다.

이때 현재 대기 학생 수가 max값보다 크다면, 이는 현재가 최대임을 의미한다. 따라서, max값을 현재 q.size()로 갱신하고 cnt값도 q의 가장 뒤에 있는 값인 q.back()으로 갱신한다.

현재 대기 학생 수가 max값과 동일한 경우에는 cnt값을 현재 q.back()과 비교해보아야 한다. 만일 cnt값이 더 크다면, 현재 q.back()으로 값을 경신하도록 한다.

 

4) 위 연산이 모두 종료되었다면, 최종적으로 저장된 max와 cnt를 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;

//백준 26042번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;

	queue<int> q;
	int max = 0;
	int cnt = 1000;
	for (int i = 0; i < n; i++) {
		int com, num;
		cin >> com;

		if (com == 1) {
			cin >> num;
			q.push(num);
		}
		else {
			q.pop();
		}

		if (max < q.size()) {
			max = q.size();
			cnt = q.back();
		}
		else if (max == q.size()) {
			if (cnt > q.back()) {
				cnt = q.back();
			}
		}
	}
	cout << max << " " << cnt << endl;
}

 

제출 결과

(2022.11.20 백준 26042번 문제 제출 결과)

이런 문제에 헤맸다니... 귀엽고만