[선형] 9. 스택

스택 구현은 쉬운데 활용해서 문제푸는게 너무 어렵다. 문제 여러번 복습하고 많이 풀기

1. 스택 (Stack)

나중에 넣은 데이터가 먼저 나오는 LIFO(Last In First Out) 기반의 선형 자료 구조
데이터 전체 획득 / 비어 있는지 확인 : Stack.getBuffer(), Stack.isEmpty()
추가 / 삭제 / 마지막 데이터 조회 / 크기 확인 : Stack.push(), Stack.pop(), Stack.peak(), Stack.size()
데이터 위치 / 준재 여부 확인 : Stack.indexOf(), Stack.includes()

2. 스택 구현하기

getBuffer(), isEmpty()

// Stack() : 생성자 함수
function Stack(array){
    this.array = array ? array : []
}

// getBuffer() : 객체 내 데이터 셋 반환
Stack.prototype.getBuffer = function(){
    return this.array.slice()
}

// isEmpty() : 객체 내 데이터 o/x
Stack.prototype.isEmpty = function (){
    return this.array.length ===0
}

let stack = new Stack([1,2,3])

console.log(stack) //Stack { array: [ 1, 2, 3 ] }

let data= stack.getBuffer()
console.log(data) //[ 1, 2, 3 ]

console.log(data === stack.array) // false
console.log(Object.getOwnPropertyDescriptors(Stack.prototype))

push(), pop(), peak(), size()

// push() : 데이터 추가
Stack.prototype.push = function(element){
    return this.array.push(element)
}

// pop() : 데이터 삭제
Stack.prototype.pop = function() {
    return this.array.pop()
}

// peak() : 가장 끝 데이터 반환
Stack.prototype.peak = function(){
    return this.array[this.array.length-1]
}

// size() : 스택 내 데이터 개수 확인
Stack.prototype.size = function(){
    return this.array.length
}

let stack = new Stack([1,2,3])
console.log(stack) //Stack { array: [ 1, 2, 3 ] }

stack.push(4)
console.log(stack) //Stack { array: [ 1, 2, 3, 4 ] }

stack.pop()
console.log(stack) //Stack { array: [ 1, 2, 3 ] }
console.log(stack.peak()) //3
console.log(stack.size()) //3

indexOf(), includes()

// indexOf() : 매개변수로 넣어온 element 위치 확인
Stack.prototype.indexOf = function (element, position = 0) {
  for (let i = position; i < this.array.length; i++) {
    if (element === this.array[i]) return i;
  }
  return -1;
  // return this.array.indexOf(element, position)
};

// includes() : 데이터 존재 여부 확인
Stack.prototype.includes = function (element) {
  for (let i = 0; i < this.array.length; i++) {
    if (element === this.array[i]) return true;
  }
  return false;
};

let stack = new Stack([1, 2, 3]);
console.log(stack); //Stack { array: [ 1, 2, 3 ] }

console.log(stack.indexOf(2)); //1

console.log(stack.includes(4)); //false
console.log(stack.includes(3)); //true

3. 문제 - 기차 운행

오른쪽 그림처럼 열차가 들어갔다 나올 수 있는 플랫폼이 있다.
열차가 1번부터 3번까지 순서대로 들어온다고 했을 때, 입력 순서대로 나갈 수 있는지 없는지 판단하는 프로그램을 작성하시오.
입력은 차량 순서 번호가 적혀 있는 배열이며, 가능 여부에 따라 true/false 를 반환한다.

function answer(train) {
  // 코드 구현 시작 영역
  let input_order = [1, 2, 3];
  let temp = [];
  for (let i = 0; i < 3; i++) {
    if (input_order[i] === train[i]) {
      temp.unshift(null);
    } else {
      temp.unshift(input_order[i]);
    }
  }
  for (let i = 0; i < 3; i++) {
    if (temp[i] !== null) {
      if (temp[i] !== train[i]) {
        return false;
      }
    }
  }
  return true;
  // 코드 구현 종료 영역
}

let input = [
  [1, 2, 3],
  [3, 2, 1],
  [3, 1, 2],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 true
// #2 true
// #3 false

// 메소드 활용하여 가독성 증가시키기
function answer(train) {
  let stack = [];
  let num = 0;

  for (let i = 0; i < train.length; i++) {
    while (stack.length == 0 || stack[stack.length - 1] < train[i]) {
      stack.push(++num);
    }
    if (stack[stack.length - 1] == train[i]) {
      stack.pop();
    } else {
      return false;
    }
  }
  return true;

  // 코드 구현 종료 영역
}

if (!Array.prototype.peak) {
  Array.prototype.peak = function () {
    return this[this.length - 1];
  };
}
if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(train) {
  let stack = [];
  let num = 0;

  for (let i = 0; i < train.length; i++) {
    while (stack.isEmpty() || stack.peak() < train[i]) {
      stack.push(++num);
    }
    if (stack.peak() == train[i]) {
      stack.pop();
    } else {
      return false;
    }
  }
  return true;

  // 코드 구현 종료 영역
}

4. 문제 - 괄호 짝 찾기 🤭

계산 수식이 주어졌을 때, 같은 짝의 괄호 위치를 찾는 프로그램을 제작하시오.
입력은 계산 수식으로 주어지며, 괄호의 짝 별 위치를 [시작, 끝]으로 찾아 2차원 배열 형태로 반환한다.
위치 시작 값은 0으로 시작하며, 하나라도 짝이 맞지 않을 경우 빈 배열을 반환한다.

if (!Array.prototype.peak) {
  Array.prototype.peak = 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 = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] == "(") {
      stack.push(i);
    } else if (str[i] == ")") {
      if (stack.isEmpty()) {
        return [];
      }
      result.push([stack.pop(), i]);
    }
  }

  if (!stack.isEmpty()){
      return []
  }

  // 코드 구현 종료 영역
  return result;
}

let input = [
  "(a+b)",
  "(a*(b+c)+d)",
  "(a*(b+c)+d+(e)",
  "(a*(b+c)+d)+e)",
  "(a*(b+c)+d)+(e*(f+g))",
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 [ [ 0, 4 ] ]
// #2 [ [ 3, 7 ], [ 0, 10 ] ]
// #3 []
// #4 []
// #5 [ [ 3, 7 ], [ 0, 10 ], [ 15, 19 ], [ 12, 20 ] ]

오 push 는 ( 일 때만 하고 ) 들어올 때 pop 한다는 개념이 너무 신선하다. 기억해두기!

5. 문제 - 접시 꺼내기 🤭

접시가 a,b,c,d 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b,a,c,d 순으로 꺼내기 위해서는
push,push,pop,pop,push,pop,push,pop 순으로 꺼내면 된다.
세척기에 꺼내야 하는 접시의 순서가 주어질 때, push/pop으로 접시가 꺼내 져야 하는 동작ㅇ르 계산하는 프로그램을 작성하시오.
입력은 접시의 수가 10개를 넘기지 않는 소문자 알파벳으로 수어지며,
접시 꺼내는 push/pop 연산 동작을 push = 0, pop = 1로 변환하여 배열을 반환한다.
(단, 주어진 순서로 못 꺼낼 경우, 빈 배열로 반환)

if (!Array.prototype.peak) {
  Array.prototype.peak = function () {
    return this[this.length - 1];
  };
}
if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(str) {
  let result = [];

  // 1. 접시의 순서 abcd ... 문자열
  // 2. 꺼내야 하는 접시, 세척기 안에 있는 알파벳보다 작을때 까지 push
  // 3. 최 상단 접시와 비교

  let stack = [];
  let dish = str.split("").sort().join("");
  let dish_index = 0;

  for (let i = 0; i < str.length; i++) {
    while (stack.isEmpty() || stack.peak() < str[i]) {
      stack.push(dish[dish_index++]);
      result.push(0);
    }

    if (stack.isEmpty() || stack.peak() > str[i]) {
      return [];
    } else {
      stack.pop();
      result.push(1);
    }
  }
  // 코드 구현 종료 영역
  return result;
}

let input = ["bacd", "dabc", "edcfgbijha"];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 [ [ 0, 4 ] ]
// #2 [ [ 3, 7 ], [ 0, 10 ] ]
// #3 []
// #4 []
// #5 [ [ 3, 7 ], [ 0, 10 ], [ 15, 19 ], [ 12, 20 ] ]

6. 문제 - 기린의 시야 🤭

기린이 앞쪽만 볼 수 있는 경우, 다른 기린을 몇 마리 볼 수 있는지 총합을 구하는 프로그램을 작성하시오.
기린은 자신보다 작거나 같은 기린만 볼 수 있으며, 자신보다 큰 기린이 나올 경우 앞 기린들이 가려서 볼 수가 없다.
입력은 기린 별 키 값이 들어오며, 달느 기린을 볼 수 있는 총합을 구해 반환한다.
예를 들어 5,2,4,2,6,1 순의 기린 키가 입력으로 들어오면 1번 기린으 2,3,4 기린을 볼 수 있어 3마리, 2번은
볼 수 있는 기린이 없고, 3번은 1마리, 4번은 0마리, 5번은 1마리, 마지막 기린은 앞의 기린이 없으므로 0마리로, 답은 총 5마리 기린이다.

if (!Array.prototype.peak) {
  Array.prototype.peak = function () {
    return this[this.length - 1];
  };
}
if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(giraffe) {
  let result = 0;

  let stack = [];
  giraffe.push(Number.MAX_SAFE_INTEGER);
  for (let i = 0; i < giraffe.length; i++) {
    while (!stack.isEmpty() && stack.peak()["h"] < giraffe[i]) {
        result += i - stack.pop()["i"] - 1
    }
    stack.push({ h: giraffe[i], i: i });
  }
  // 코드 구현 종료 영역
  return result;
}

let input = [
  [10, 3, 7, 4, 12, 2],
  [7, 4, 12, 1, 13, 11, 12, 6],
  [20, 1, 19, 18, 15, 4, 6, 8, 3, 3],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 5
// #2 6
// #3 30

7. 문제 - 괄호 계산 🤭

4개의 기호 (,),[,] 를 이용해서 만들어지는 괄호열로, 아래 규칙으로 계산하는 프로그램을 작성하시오

'()' 인 괄호 열 값은 2
'[]' 인 괄호 열 값은 3
'(x)' 인 괄호 열 값은 2 * X
'[x]' 인 괄호 열 값은 3 * x
()[] 는 () + []

예를 들어 ()[[] 는 2+3*3 = 11 이다.
만약 쌍이 맞지 않거나 기호 순서가 비정상적이라 올바른 괄호 셋이 만ㄷ르어지지 않는 경우에는 0을 반환한다.
입력은 4개의 기호로만 이루어진 괄호가 문자열 형태로 주어지며, 계산을 통해 나온 정수를 반환한다.

if (!Array.prototype.peak) {
  Array.prototype.peak = function () {
    return this[this.length - 1];
  };
}
if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function () {
    return this.length == 0;
  };
}

function answer(str) {
  let result = 0;

  // ( > x2
  // [ > x3
  // ) > /2
  // ] > /3
  // () or [], 현재 temp값을 result에 더해준다.

  let stack = [];
  let temp = 1;

  for (let i = 0; i < str.length; i++) {
    let mark = str[i];

    switch (mark) {
      case "(":
        temp *= 2;
        stack.push(mark);
        break;
      case "[":
        temp *= 3;
        stack.push(mark);
        break;
      case ")":
        if (stack.isEmpty() || stack.peak() != "(") {
          return 0;
        }
        if (str[i - 1] == "(") {
          result += temp;
        }
        stack.pop();
        temp /= 2;
        break;
      case "]":
        if (stack.isEmpty() || stack.peak() != "[") {
          return 0;
        }
        if (str[i - 1] == "[") {
          result += temp;
        }
        stack.pop();
        temp /= 3;
        break;
    }
  }

  if (!stack.isEmpty()) {
    return 0;
  }
  // 코드 구현 종료 영역
  return result;
}

let input = ["(()[[]])", "[][]((])", "(()[[]])([])"];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 22
// #2 0
// #3 28

이 문제는 정말 왜 이런 풀이로 변형되는지 이해가 안간다..ㅠㅠ 다시 시도해보기!

자료구조 문제를 풀 때는 해당 자료구조 구현법을 그대로 쓰는 것이 아닌, 그 특성을 활용하여 새로운 해결법으로 만들 것..!