스택 문제풀이 - 기린의 시야

✏️ 문제

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

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

📝 풀이

// 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(giraffe) {
  let result = 0;

  let stack = [];
  giraffe.push(Number.MAX_SAFE_INTEGER);
  for (let i = 0; i < giraffe.length; i++) {
    while (!stack.isEmpty() && stack.peek()["h"] < giraffe[i]) {
      // 볼 수 있는 기린 수 계산
      result += i - stack.pop()["i"] - 1;
    }
    // 높이 계산 값과 인덱스 위치 push
    stack.push({ h: giraffe[i], i: i });
  }

  return result;
}

1. 자신보다 높은 기린이 나왔을 경우 앞을 볼 수 없으니 이 점을 참고해서 자신보다 높은 기린이 나왔을 경우에 사이에 있는 기린을 계산하는 코드를 작성해야한다.
2. giraffe 라는 배열에 가장 큰 양의 정수를 넣어준다. (Number.MAX_SAFE_INTEGER)
3. for문으로 순회하며, while문 으로 stack에 있는 기린이 작은지 계산을 하도록 작성한다.
4. 계산 후 몇번째 인덱스인지 알아야지 처음 말했던 사이에 있는 기린 수를 계산할 수 있으니 인덱스를 찾을 수 있도록 push를 해 줄때 인덱스 번호도 같이 push한다.