BOJ 26042 (S5) 식당 입구 대기 줄

문제 요약

주어진 n개의 식당 현황 정보에 따라, 가장 줄이 길었을 때의 학생 수와 당시 맨 뒤 학생의 번호를 출력해보자.
(단, 줄이 길었을 때가 여러 번이라면 맨 뒤 학생의 번호가 가장 작은 경우를 출력한다.)

풀이 방향

1 a: 번호가 a번인 학생이 이어서 줄을 선다.
2: 맨 앞 학생이 식사를 한다. (줄에서 탈출!)

두 정보가 적절히 섞여, 총 n개의 정보가 주어진다.

식당에서 줄을 서고 밥을 먹는 과정은 선입선출(FIFO), 즉 queue 형태로 생각할 수 있다.
1 a 의 경우 queue.push(a); 를,
2의 경우 queue.pop(); 을 차근차근 진행하면 된다.

제출 답안

#include <iostream>
#include <queue> //queue, vector
#include <algorithm> //pair, sort
using namespace std;

int main() {
    int t,num,a;
    cin >> t;
    queue<int> q;
    vector<pair<int,int>> v(t); // <q.size(),q.back()>
    for(int i=0; i<t; i++) {
        cin >> num;
        if(num==1) {
            cin >> a;
            q.push(a);
            v[i].second = a;
        }
        else {
            q.pop();
        }
        v[i].first -= q.size(); //오름차순 정렬 예정이라 음의 방향으로 넣기
    }
    sort(v.begin(),v.end());
    cout << v[0].first*(-1) << ' ' << v[0].second; // pair 출력 (음수값은 양수로)
    return 0;
}

답안 해설

단순히 push&pop만 할 뿐만 아니라 정보마다 현재 줄의 길이와 끝 번호를 저장해야 되기 때문에, 나는 동시에 저장하고 불러오기 위해서 pair를 선택했다.

모든 케이스를 돌면서 저장하고, 최종적으로 줄 길이가 큰 순서로 정렬하고자 했다.

하지만 단순히 내림차순 정렬하면, 만약 v[0].first==v[1].second 인 경우에는 끝 번호 값인 pair.second를 확인해서 작은 값을 선택해야 하는데, 사용자 정의 함수를 사용하지 않고 앞은 내림차순 뒤는 오름차순 이런 형태로 쉽게 정렬하기는 어려웠다.

고민 끝에 나는 int의 특성을 활용했다.
양수는 절댓값이 클 수록 값이 크지만, 음수는 절댓값이 작을 수록 값이 크다. 즉, 어느 한 쪽 값에 -1을 곱해서 할당한 후, 한 방향으로 정렬하면 원하고자 하는 값을 쉽게 구할 수 있었다.

나는 pair와 sort에 대한 여러가지 문제를 풀어보다가 오름차순+내림차순이 섞여서 등장하는 정렬에 대해 쉽게 접근하고자 고민한 끝에 이 방법을 얻을 수 있었다. 다만 이 방식은 +,- 등 스칼라 값으로 비교가 가능한 int형 등등에 한해서 적용할 수 있다. string형에는 사용이 불가능하다.

추가로, 다른 사람들의 풀이를 보면 대부분이 케이스마다 줄 길이의 최댓값이 변경될 때마다 끝 번호를 비교해서 작으면 새롭게 저장하는 방식을 선택했다. 선택은 자유!

이 문제와 관련된 좋은 문제
BOJ 1966 (S3) 프린터 큐
BOJ 15828 (S4) Router

추가로 읽어보면 좋은 내용

• vector와 pair
• algorithm-sort로 정렬해보기