[algo / neet] Min stack

알고리즘

목록 보기

9/11

C++ 정리

클래스 멤버 변수

class MinStack {
public:
    MinStack() {
        stack<int> st;
        int mn = std::numeric_limits<int>::min();
    }
    
    void push(int val) {
        min_pq.push(val);
        st.push(val);
    }
    
    ...
};

위와 같은 코드로 작성하니 컴파일 오류가 남.

st와 min_pq 변수를 생성자(MinStack()) 내부에서 선언했기 때문 (지역 변수)
생성자라도 지역 변수를 선언하면 해당 생성자 함수 끝나면 메모리에서 사라짐
push등의 함수에서는 st와 min_pq 변수를 undeclared identifier 로 인식하여 컴파일 에러 발생

클래스의 모든 멤버 함수에서 접근하려면 클래스 멤버 변수로 선언해야 됨

선언과 동시에 초기화하는 방식 (In-class initializer)

	#include <stack>
	#include <climits>
	
	class MinStack {
	private:
	    // 선언과 동시에 기본값으로 초기화
	    std::stack<int> st;
	    int mn = INT_MAX;
	
	public:
	    MinStack() {
	        // 생성자 본문을 비워두어도 알아서 위 기본값으로 세팅됨
	    }
	
	    void push(int val) { /* ... */ }
	};

생성자 멤버 초기화 리스트(Member Initializer List)를 사용

	#include <stack>
	#include <climits>
	
	class MinStack {
	private:
	    std::stack<int> st;
	    int mn;
	
	public:
	    // 콜론(:) 뒤에서 st와 mn을 초기화
	    MinStack() : st(), mn(INT_MAX) {
	        // 생성자 본문
	    }
	
	    void push(int val) { /* ... */ }
	};

생성자 본문에서 값 대입

	#include <stack>
	#include <climits>
	
	class MinStack {
	private:
	    std::stack<int> st;
	    int mn;
	
	public:
	    MinStack() {
	        // 생성자 본문 내에서 값 대입
	        mn = INT_MAX;
	    }
	
	    void push(int val) { /* ... */ }
	};

접근 제어자(private:) 생략 방식 (기본 private 특성 활용)
- class 기본값 때문에 private: 키워드를 작성하지 않아도 자동으로 private 처리됨

	#include <stack>
	#include <climits>
	
	class MinStack {
	    // private: 생략 (자동으로 private 지정됨)
	    std::stack<int> st;
	    int mn = INT_MAX;
	
	public:
	    MinStack() {
	        // 생성자
	    }
	
	    void push(int val) { /* ... */ }
	};

`int` 타입의 최댓값과 최솟값 선언하기

(C 스타일 상수) <climits> 헤더를 사용
C++ 표준 템플릿을 이용하는 방법 : <limits>
- 다른 자료형(long long, double 등)으로 확장하여 사용할 때 유용함

#include <iostream>
#include <climits> // INT_MIN, INT_MAX 정의된 헤더
#include <limits> // std::numeric_limits 정의된 헤더

int main() {
    int c_min_val = INT_MIN; // int의 가장 작은 값 (-2,147,483,648)
    int c_max_val = INT_MAX; // int의 가장 큰 값   (2,147,483,647)

	int cpp_min_val = std::numeric_limits<int>::min(); // int의 가장 작은 값
	int cpp_max_val = std::numeric_limits<int>::max(); // int의 가장 큰 값
    
    return 0;
}

풀이

class MinStack {
    stack<int> st;
    stack<int> min_st;
public:

    MinStack() : st(), min_st() { }
    
    void push(int val) {
        st.push(val);

        if (min_st.empty()) min_st.push(val);
        else if (min_st.top() > val) min_st.push(val);
        else if (min_st.top() <= val) min_st.push(min_st.top());
    }
    
    void pop() {
        min_st.pop(); st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
};