Leetcode Java Min Stack

문제

Link

코드

class MinStack {

  private Node node;

  /** initialize your data structure here. */
  public MinStack() {
  }

  public void push(int val) {
    if (node == null) {
      node = new Node(val, val, null);
    } else {
      node = new Node(val, Math.min(val, node.min), node); 
    }
  }

  public void pop() {
    node = node.prev;
  }

  public int top() {
    return this.node.val;
  }

  public int getMin() {
    return this.node.min;
  }

}

public class Node {

  public int val;
  public int min;
  public Node prev;

  public Node() {
  }

  public Node(int val, int min, Node prev) {
    this.val = val;
    this.min = min;
    this.prev = prev;
  }

}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

결과

Link

설명

1. 아래의 메서드를 구현하는 문제이다.
   • 생성자인 MinStack()은 Stack 객체를 초기화 한다.
   • 메서드인 push(val)은 val을 Stack에 넣는다.
   • 메서드인 pop()은 Stack의 가장 마지막 값을 제거한다.
   • 메서드인 top()은 Stack의 가장 첫 값을 반환한다.
   • 메서드인 getMin()은 Stack의 최솟값을 반환한다.
2. 문제 풀이에 기본이 되는 Node 객체를 선언한다.
   • Node는 현재 값, 최솟값, 이전 Node를 저장할 수 있다.
   • 생성자를 통해 위의 기본 변수들의 값을 넣을 수 있다.
3. push(val) 메서드를 구현한다.
   • 전역 변수인 node가 null인 경우, 새로운 Node를 val값으로 생성하여 node에 넣어준다.
   • 전역 변수인 node가 null이 아닌 경우, 새로운 Node를 전역 변수 node와 val 값, val 값과 node.min 값 중 가장 작은 값으로 생성하여 node에 넣어준다.
4. pop() 메서드를 구현한다.
   • 전역 변수인 node에 node.prev를 넣어 마지막 Node의 연결을 끊어준다.
5. top() 메서드를 구현한다.
   • 전역 변수인 node의 val 값을 반환한다.
6. getMin() 메서드를 구현한다.
   • 전역 변수인 node의 min 값을 반환한다.

참고

해당 문제는 요구 조건을 만족하는 Stack을 구현하는 문제로, java.util.Stack을 사용하는 것은 문제 취지에 맞지 않는 것으로 판단된다.

소스

Sample Code는 여기에서 확인 가능합니다.