스택 문제풀이 - 접시 꺼내기

✏️ 문제

접시가 a, b, c, d 순으로 한쪽이 막혀있는 세척기에 들어간다고 할 떄, b a c d 순으로 꺼내기 위해서는 push, push, pop, pop, push, pop, push, pop 순으로 꺼내면 된다.
세척기에 꺼내야 하는 접시의 순서가 주어질 때, push/pop으로 접시가 꺼내져야 하는 동작을 계산하는 프로그램을 작성하시오.
입력값

bacd
dabc
edcfgbijha

📝 풀이

// prototype 생성
if (!Array.prototype.peek) {
  Array.prototype.peek = function () {
    return this[this.length - 1];
  };
}

if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(str) {
  let result = [];
  let stack = [];
  // 1. 접시의 순서 abcd... 순서대로 문자열을 만들어준다.
  let dish = str.split("").sort().join("");
  // dish에 대한 index 변수
  let dish_index = 0;

  // 반복문을 순회하며 str의 i 값을 확인한다.
  for (let i = 0; i < str.length; i++) {
    while (stack.isEmpty() || stack.peek() < str[i]) {
      // 세척기 안에 push, result에 기록해준다.
      stack.push(dish[dish_index++]);
      result.push(0);
    }

    // 만약 순회를 마친 후
    if (stack.isEmpty() || stack.peek() > str[i]) {
      return [];
    } else {
      stack.pop();
      result.push(1);
    }
  }

  return result;
}

1. 접시의 순서 abcd... 순서대로 문자열을 만들어준다.
2. 꺼내야 하는 접시는 세척기 안에 있는 알파벳이 작을 때 계속해서 push를 해줘야한다.
3. 최상단에 있는 순서대로 있는 문자열과 비교하여 판단한다.