[99클럽 4기 코테 스터디 TIL 18일차] 식당 입구 대기 줄 (feat. 스택으로 식당 줄 서기)

1) 문제

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

여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.

학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 출력하자. 대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력하자.

A에 저장된 n개의 정보는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2이다.

• 1 a: 학생 번호가 양의 정수 a인 학생 1명이 학교 식당에 도착하여 식당 입구의 맨 뒤에 줄을 서기 시작한다.
• 2: 식사 1인분이 준비되어 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식사를 시작한다.

식사 1인분이 준비될 때는 식당 입구에서 대기 중인 학생이 항상 존재한다. 식당 입구에 줄을 서서 대기하였으나 식사가 준비 안 된 학생은 식사를 못 한다.

입력

첫 번째 줄에 n이 주어진다.

다음 줄부터 n개의 줄에 걸쳐 한 줄에 하나의 정보가 주어진다. 주어지는 정보는 유형 1, 2중 하나이다.

출력

첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 빈칸을 사이에 두고 순서대로 출력한다. 대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력한다.

제한

• 1 ≤ n ≤ 100,000
• A에는 유형 1, 유형 2만 저장되어 있다.
• 1 ≤ a ≤ n, 모든 양의 정수 a의 값은 서로 다르다.

예제 입력 1 복사

5
1 2
1 1
2
1 3
2

예제 출력 1 복사

2 1

첫 번째 1 2를 처리한 후, 대기 줄은 2가 된다.

두 번째 1 1을 처리한 후, 대기 줄은 2 1이 된다. 대기줄 2 1은 2번 학생이 앞쪽, 1번 학생이 뒤쪽에서 대기 중임을 의미낸다.

세 번째 2를 처리한 후, 앞쪽에서 대기 중인 2번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 1이 된다.

네 번째 1 3을 처리한 후, 대기 줄은 1 3이 된다.

다섯 번째 2를 처리한 후, 앞쪽에서 대기 중인 1번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 3이 된다. 

다섯 개의 정보를 처리하는 동안 대기 줄에 대기하는 학생 수의 최댓값은 2이다. 학생 수가 2인 대기 줄은 '2 1', '1 3' 두 가지이며, 맨 뒤에 줄 서 있는 학생 번호가 가장 작은 경우는 ‘2 1’이다.

 

 

 

2) 내가 구현한 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        LinkedList<String> queue = new LinkedList<>();

        int maxCnt = 0;
        String lastPerson = "";

        int n = Integer.parseInt(br.readLine());

        //1 a: 학생 번호가 양의 정수 a인 학생 1명이 학교 식당에 도착하여 식당 입구의 맨 뒤에 줄을 서기 시작한다.
        //2: 식사 1인분이 준비되어 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식사를 시작한다.
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            String method = "";
            String person = "";

            if(str.contains(" ")) {
                method = str.split(" ")[0];
                person = str.split(" ")[1];
            }else{
                method = str;
            }

            switch(method) {
                case "1":
                    queue.add(person);
                    break;
                case "2":
                        queue.poll();
                    break;
            }

            if(maxCnt < queue.size()) {
                maxCnt = queue.size();
                lastPerson = queue.peekLast();
            } else if(maxCnt == queue.size()) {
                if(Integer.parseInt(lastPerson) > Integer.parseInt(queue.peekLast())) lastPerson = queue.peekLast();
            }
//            bw.write(i + ":"+queue+"\n");
        }

        bw.write(maxCnt + " "+lastPerson);
        bw.flush();
        br.close();
        bw.close();

    }
}

 

 

3) 추가 문제

미들러 - 센

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

챌린저 - 상담원 인원

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스