[99클럽] 코딩테스트 스터디, 14일차 TIL - 비기너 (백준, 26042)

 

1. 문제풀이

1) 문제, 식당 입구 대기 줄 (백준 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번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 빈칸을 사이에 두고 순서대로 출력한다. 대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력한다.

 

 

2) 해석

 

- 대기하는 학생 수가 최대인 순간의 학생 수와 이때 식당 입구 맨 뒤에 대기 중인 학생의 번호를 출력
- 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우 출력

- 첫 번째 = n = 반복 횟수
- 두 번째부터 = A = 정보
- A는 두 가지 유형이 존재

 

- 학생 1명이 학교 식당에 도착해 입구 맨 뒤에 줄을 선다

- 맨 앞 학생 1명이 식사를 한다.

 

- A[0] = 유형번호

- A[1] = 학생 번호

 

type = 1이면, 학생번호를 waitingLine에 추가
type = 2면, waitingLine 맨 앞 빼기

 

 

1) 처음 접근 방법

 

우선 처음 접근부터 잘못했다..

문제에서 필요한 것은 "길이"와 "학생 수"이다.

그리고 문제를 풀 때 필요한 것도 현재 길이와 학생 수이다.

이걸 간과하고 무조건 배열로 풀려고 시도했다가 계속 테스트 오류 나서 다른 방법으로 바꿨다.

 

값이 더 큰 숫자로 배열을 복사해서 붙여넣었더니 테스트는 맞는데 어디선가 계속 오류가 나더라ㅠ

근데 생각해보면 배열 복사해서 붙여 넣는 게 성능도 더 안 좋고 해서 다른 방법을 시도해 봤다.

 

 

2) 두 번째 접근 방법

 

두 번째로 접근한 방법은 최대 길이와 학생 번호를 숫자로 받는 방법이었다.

풀이는 비슷했는데 이것만 바꾸니까 바로 통과되더라ㅎ

 

 

3) 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const arr = input.slice(1);
const waitLine = [];
let maxLen = 0;
let lastStudentNumber = -1;

arr.forEach((A) => {
  const [type, number] = A.split(" ");

  if (type == 1) waitLine.push(number);
  else if (waitLine.length > 0) waitLine.shift();

  const waitLen = waitLine.length;

  if (waitLen > maxLen) {
    maxLen = waitLen;
    lastStudentNumber = waitLine[waitLen - 1];
  } else if (waitLen === maxLen) {
    lastStudentNumber = Math.min(lastStudentNumber, waitLine[waitLen - 1]);
  }
});

console.log(maxLen, lastStudentNumber);

 

const arr = input.slice(1);
const waitLine = [];
let maxLen = 0;
let lastStudentNumber = -1;

 

우선 forEach를 사용하기 위해서 arr 배열을 만들어줬다.

여기에는 N을 제외한 A가 전부 담기게 된다.

 

그 후, 현재 대기 줄을 담을 waitLin을 만들어줬다.

최대 대기줄을 담을 Len과, 마지막 학생 번호를 담을 lastStudentNumber도 만들어줬다.

 

 

const [type, number] = A.split(" ");

if (type == 1) waitLine.push(number);
else if (waitLine.length > 0) waitLine.shift();

 

이제 배열을 반복해서 돌면서 조건문을 구현해 주면 된다.

 

우선, A[0]은 유형, A[1]은 학생 번호이기 때문에 각각 변수로 만들어줬다.

그리고 1 유형인 경우, waitLine에 학생 번호를 넣어줬다.

그리고 2 유형인 경우, waitLine에 길이가 있다면 맨 앞에 있는 숫자를 빼줬다.

 

const waitLen = waitLine.length;

if (waitLen > maxLen) {
  maxLen = waitLen;
  lastStudentNumber = waitLine[waitLen - 1];
} else if (waitLen === maxLen) {
  lastStudentNumber = Math.min(lastStudentNumber, waitLine[waitLen - 1]);
}

 

이제 waitLine의 길이가 maxLen보다 길면, 해당 길이를 maxLen에 넣어주고

lastStudentNumber도 waitLine의 마지막 학생 번호로 변경해 줬다.

 

그리고 길이가 같다면, 더 작은 학생 번호를 lastStudenNumber에 넣어줬다.

 

 

 

- 걸린 시간

 

실제로 이 정도 시간이 걸린 건 아니고.. 중간에 쉬었다가 해서ㅎ

근데 오래 걸린 것도 맞음ㅠㅠ

 

 

2. 리팩토링

문제를 풀고 나서 걸린 시간을 봤는데 생각보다 너무 오래 걸렸다ㅠㅠ

그래서 방법이 있지 않을까 해서 다른 사람 코드를 살펴봤다.

그랬더니 역시나! 다른 방법이 있었다.

const fs = require("fs");
const input = fs.readFileSync("./index.txt").toString().trim().split("\n");

const arr = input.slice(1);

let waitLen = 0;
let maxLen = 0;
let lastStudentNumber = -1;

arr.forEach((A) => {
  const [type, number] = A.split(" ");

  if (type == 1) {
    waitLen++;

    if (waitLen > maxLen) {
      maxLen = waitLen;
      lastStudentNumber = number;
    } else if (waitLen === maxLen) {
      lastStudentNumber = Math.min(lastStudentNumber, number);
    }
  } else {
    if (waitLen > 0) waitLen--;
  }
});

console.log(maxLen, lastStudentNumber);

 

기존 코드와 크게 다르지 않지만, 가장 크게 바뀐 것은 waitLine을 배열로 받지 않는 것이다.

사실 waitLine을 전체 배열로 저장할 필요는 없다.

 

우리는 waitLine의 길이와 maxLen의 길이를 비교해서 가장 대기줄이 긴 것을 출력하면 된다.

즉 둘 다 길이만 필요한 것이다. 

 

따라서 waitLine을 waitLen으로 수정해서 숫자로 입력받도록 했다.

이렇게 하면 shift()처럼 배열을 조작하지 않아도 되니까 시간 복잡도가 줄어든다. 

 

이로 인해 원래는 O(n^2)이던 시간 복잡도가 O(n)으로 줄어들었다!