99클럽 코테 스터디 18일차 TIL + 큐(C++)

문제

[백준] 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의 최솟값을 갱신해주어야 한다.