문제
[백준] 26042번: 식당 입구 대기 줄
https://www.acmicpc.net/problem/26042
첫 시도 (실패)
#include <iostream>
#include <queue>
using namespace std;
int main() {
int N;
cin >> N;
queue<int> q;
int ans_size = 0; // 대기하는 학생 수
int ans_num = 100001; // 대기하는 학생 수가 최대일 때 맨 뒤에 대기 중인 번호
while (N--) {
int type, num;
cin >> type;
if (type == 1) {
cin >> num;
q.push(num);
}
if (type == 2) {
q.pop();
continue;
}
if (q.size() >= ans_size) {
ans_size = q.size();
ans_num = min(q.back(), ans_num);
}
}
cout << ans_size << ' ' << ans_num;
return 0;
}
큐 문제인 걸 떠올리기까지는 어렵지 않은데, 약간 함정이 있는 문제인 것 같다.
처음엔 왜 이렇게까지 정답율이 낮지? 했는데 틀리고 나니 이해가 됐다.
틀린 이유
대기학생 수가 최대일 때만 학생 번호를 업데이트 해줘야 하는데,
위 코드에서는 ans_size
이상이기만 하면 학생 번호를 최솟값으로 업데이트한다.
이렇게 작성하는 경우, 만약 첫 입력이 1 1
이어서 큐에 1
이 들어온다면 ans_num
이 1
로 설정되는 바람에
이후 ans_size
가 최댓값으로 업데이트 되어도 ans_num
이 끝까지 1
에서 업데이트되지 않을 수 있다.
코드 (정답)
#include <iostream>
#include <queue>
using namespace std;
int main() {
int N;
cin >> N;
queue<int> q;
int ans_size = 0; // 대기하는 학생 수
int ans_num = 100001; // 대기하는 학생 수가 최대일 때 맨 뒤에 대기 중인 번호
while (N--) {
int type, num;
cin >> type;
if (type == 1) {
cin >> num;
q.push(num);
}
if (type == 2) {
q.pop();
continue;
}
// 대기 학생 수가 최대일 때만 ans_num을 업데이트
if (q.size() > ans_size) {
ans_size = q.size();
ans_num = q.back();
} else if (q.size() == ans_size) {
ans_num = min(ans_num, q.back());
}
}
cout << ans_size << ' ' << ans_num;
return 0;
}
위와 같이 대기 학생 수가 최대를 갱신했을 때만 ans_num
을 업데이트해주고,
대기 학생 수가 ans_size
와 같으면 그때 min 함수로 ans_num
의 최솟값을 갱신해주어야 한다.
'99클럽 TIL' 카테고리의 다른 글
99클럽 코테 스터디 20일차 TIL + 완전탐색(C++) (0) | 2024.11.16 |
---|---|
99클럽 코테 스터디 19일차 TIL + 힙(C++) (0) | 2024.11.15 |
99클럽 코테 스터디 17일차 TIL + 스택/큐(C++) (6) | 2024.11.14 |
99클럽 코테 스터디 16일차 TIL + 그리디(C++) (0) | 2024.11.12 |
99클럽 코테 스터디 15일차 TIL + 스택/큐(C++) (1) | 2024.11.12 |