S4) Unit 1. [실습] Stack & Queue 문제

📣  유효한 괄호쌍

Q. 입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.

입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.

1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.

2. 열린 괄호는 올바른 순서대로 닫혀야만 한다. 3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.

입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.

const isValid = (str) => {
  const stk = [];
  if(str.length === 0 || str.length === 1) return false;
  // 빈 문자열이거나 괄호 하나면 false

  for(let i=0; i<str.length; i++){
    // 돌면서
    if(str[i] === '(' || str[i] === '{' || str[i] === '['){
      // 여는 괄호 만나면 stk에 push
      stk.push(str[i]);
    }
    else if(str[i] === ')' || str[i] === '}' || str[i] === ']'){
      // 닫는 괄호 만나면 
      if(stk.length === 0) return false;
      // 닫는 괄호 있는데 스택에 여는 괄호 없으면 false
      else {
        // 스택에 여는 괄호가 존재한다면
        let pop = stk.pop();
        // 스택에 있는거 빼서
        if((pop === '[' && str[i] !== ']') || (pop === '(' && str[i] !== ')') || (pop === '{' && str[i] !== '}')){
          // 들어온 닫힌 괄호랑 맞는 괄호인지 보고
          return false;
          // 아니면 false
        }
      }
    }
  }
 if(stk.length === 0) return true;
 // 조건문에 걸리지 않고 제대로 pop 됬다면 스택에 남아있는 게 없어야 한다.
 else return false;
 // 남아있는게 있다면 여는 괄호만 계속 나온 경우이므로 false
}

---

📣  박스 포장

Q. 마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.

불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.

뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.

만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.

이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.

function paveBox(boxes) {
  // TODO: 여기에 코드를 작성합니다.
  let outPeople = [];
  // 나간 사람 인원 수 담을 배열
  let queue = [];
  for(let i=0; i<boxes.length; i++){
    // 박스 배열 돌면서
    if(queue.length === 0){
      // 첫번째 요소이면
      queue.push(boxes[i]);
      // 큐에 푸시
    }
    else {
      // 2번째 요소부터
      if(boxes[i] <= queue[0]){
        // 만약에 앞사람 보다 박스 개수가 적으면 
        queue.push(boxes[i]);
        // 큐에 계속 푸시(같이 나갈 수 있으므로)
      }
      else if(boxes[i] > queue[0]){
        // 앞사람 보다 박수 개수가 많으면
        let people = 0;
        // 일단 그 앞에 사람들 먼저 내보낼 수 있으므로
        let len = queue.length;
        // 큐의 길이 구하고
        for(let i=0; i<len; i++){
          queue.shift();
          // 큐 요소 빼면서
          people++;
          // 나가는 사람 수도 ++ 해준다.
        }
        outPeople.push(people);
        // max 값 구해야하므로 나간 사람 배열에 일단 담아준다
        queue.push(boxes[i]);
        // 앞사람보다 박스 개수 많던 거 큐에 push
      }
    }
  }
  let people = 0;
  // 큐에 남은 사람들 담을 변수
  for(let i=0; i<queue.length; i++){
    // 큐에 남은 사람들은 boxes 배열이 다 돌아서 한번에 나갈 수 있는 사람들
    people++;
  }
  outPeople.push(people);
  return Math.max(...outPeople);
  // 그 중에 가장 많이 나간 인원수 구하기
}