스택 문제

최근에 한 회사와 전화 인터뷰를 했는데 제대로 해결하는 방법을 모르는 스택에 대한 질문을 받았습니다. 이로 인해 스택에 대한 지식이 깊어졌습니다.

스택에서 최대 값을 찾기 위해 max 함수를 작성하는 방법에 대해 생각하라는 요청을 받았습니다.

스택 리프레셔

스택은 최신 항목이 맨 위에 추가되고 항목도 맨 위에서 제거되는 데이터 구조입니다. 이를 후입선출(LIFO)이라고 합니다. 스택을 나타내는 한 가지 방법은 배열입니다. 전화 통화의 문제에 대해 생각할 때 끝에 항목이 추가되고 끝에서 제거되는 배열을 상상했습니다.

다음은 예입니다.

[2, 3, 3, 1, 1, 100, 200, 100, 400, 30]

30은 스택의 맨 위에 있고 스택에서 제거된 첫 번째 숫자이기도 합니다.

문제로 돌아가기

전화 통화 중에 나는 면접관이 찾고 있는 것이 아니라는 것을 알고 있는 몇 가지 해결책만 제시할 수 있었습니다. 내 첫 번째 분명한 생각은 배열을 반복하면서 현재 최대 수를 저장하고 마지막에 해당 수를 반환하는 것이었습니다. 이것은 분명히 면접관이 찾고 있던 것이 아니었고 다른 데이터 구조로 이 문제를 어떻게 해결할 것인지 물었습니다.

다음으로 개체를 사용할 수 있는 방법을 생각하려고 했고 연결 목록이 떠 올랐습니다. 내 아이디어는 현재 최대 수가 삭제된 경우 이전 최대 수에 대한 포인터가 있는 연결 목록에 현재 최대 값을 저장하는 것이었습니다. 한동안 연결 목록을 구현하는 방법을 검토하지 않았고 이것이 면접관이 찾고 있는 것이 아니라는 직감이 있었기 때문에 이 아이디어를 충분히 생각하지 못했습니다.

우리는 이 질문에서 다음 단계로 넘어갔고 전화를 끊은 후 답을 찾기로 결심했습니다.

인터넷 검색 후

약간의 인터넷 검색 후 면접관이 실제로 찾고 있는 것과 유사한 implementation을 발견했습니다.

이 구현을 사용하면 최대 값을 저장할 추가 스택이 생깁니다. 이 추가 스택에서 상위 값을 읽어 현재 최대값이 무엇인지 확인합니다.

예를 들어 다음과 같은 초기 스택이 주어집니다.

[3]

다음과 같은 최대 값 스택이 있습니다.

[3]

3은 지금까지 스택에 있는 유일한 숫자이므로 최대값입니다. 이제 스택에 5를 푸시하면 현재 최대값은 5가 되어야 합니다. 따라서 이를 최대값 스택에 추가합니다.

//currentStack
[3, 5]
//maxNumStack
[3, 5]

이제 현재 최대 값보다 작거나 같은 숫자를 스택에 추가한다고 가정합니다. 이제 스택의 길이를 정렬하기 위해 현재 최대값을 maxNumStack에 다시 추가합니다.

//currentStack
[3, 5, 4]
//maxNumStack
[3, 5, 5]

이렇게 하면 스택에서 4가 팝되면 maxNumStack에서 하나의 요소를 팝하고 여전히 currentMax가 무엇인지 알 수 있습니다(이 경우 5).

Max 메서드로 스택 구현

이것이 JavaScript로 이것을 구현하는 방법입니다. 푸시 및 팝 방법과 같은 스택의 기본 기능을 구현하기 위해 대략적으로 thisblog를 따랐습니다.

class Stack {
  constructor() {
    this.data = [];
    this.size = 0;
    this.maxValues = [];
  }

  push(element) {
    // if the stack is empty or the element we're pushing is greater than currentMax, add the new element to maxValues
    if (this.size === 0 || element >= this.findMax()) {
      this.maxValues.push(element)
    }
    // otherwise, push the currentMax to maxValues again, to align lengths of arrays and keep currentMax
    else {
      this.maxValues.push(this.findMax())
    }
    // increase the size variable by 1 to keep track of length, and add element to stack
    this.size += 1
    this.data.push(element);
    return this.data
  }

  pop() {
    // if the stack isn't empty, decrease the size count and remove element from the end of the stack and maxValue array to keep lengths aligned
    if (this.size > 0) {
      this.size -= 1;
      this.maxValues.pop()
      return this.data.pop()
    }
  }

  // this returns the top element in the stack (last element in the array)
  peek() {
    return this.data[this.size - 1]
  }

  // this returns the maxValue currently in the stack, by grabbing the last element of the maxValue stack
  findMax() {
    return this.maxValues[this.size - 1]
  }
}

다음은 터미널의 출력과 함께 작동하는지 테스트하기 위해 작성한 코드입니다.

let stack = new Stack()

stack.push(5)
stack.push(5)
stack.push(7)
stack.push(3)
stack.push(4)

console.log(stack)
// Stack {data: [ 5, 5, 7, 3, 4 ], size: 5, maxValues: [ 5, 5, 7, 7, 7 ]}
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5, 7, 3 ], size: 4, maxValues: [ 5, 5, 7, 7 ] }
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5, 7 ], size: 3, maxValues: [ 5, 5, 7 ] }
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5 ], size: 2, maxValues: [ 5, 5 ] }
console.log("max", stack.findMax())
// max 5

이 구현을 사용하면 이론적으로 최대값을 찾기 위해 수행하는 모든 작업은 maxValues ​​배열에서 마지막 요소를 찾기 위한 빠른 조회 작업입니다. 인덱스로 배열의 요소를 조회하는 데 걸리는 시간 복잡도는 O(1)입니다. 또한 maxValues ​​스택에서 값을 추가하고 제거하는 push() 및 pop() 작업의 시간 복잡도는 O(1)입니다. 이는 매번 현재 최대값을 찾기 위해 배열을 반복하는 것보다 훨씬 더 효율적입니다. 여기서 n은 배열의 길이입니다.

참고로 push 및 pop 메서드를 구현하는 다른 방법이 있지만 이 블로그의 초점이 아니므로 기본 제공 배열 메서드를 사용하기로 했습니다.

마무리

코드에서 스택을 사용한 시간은 언제입니까? 이 솔루션에 대해 어떻게 생각하는지, 개선할 수 있다고 생각하는지 알려주세요. 읽어 주셔서 감사합니다!