[TIL_Carrotww] 86 - 23/01/12

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode42 Trapping Rain Water hard

• 스택 풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        result = 0

        for i in range(len(height)):
            while stack and height[i] >= height[stack[-1]]:
                top = stack.pop()

                if not stack:
                    break
                distance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]

                result += distance * waters
            stack.append(i)

        return result

• 투 포인트 방식으로 푸는 방법도 있지만 이해가 잘 되지 않아 다시 풀어봐야겠다.

🧲 C++

#include <bits/stdc++.h> 란

위 헤더 파일은 모든 모든 표준 헤더 파일이 포함된 헤더 파일이다. 위 헤더 파일 한 번만 작성하면 모든 헤더파일을 사용할 수 있지만 단점으로는 불필요한 헤더파일도 추가되기 대문에 크기가 커지고 컴파일 시간이 길어진다는 단점이 있다.

우분투 아래 경로에 stdc++.h 파일에서 어떤 헤더들이 있는지 확인할 수 있다.
/usr/include/x86_64-linux-gnu/c++/7/bits
// C++

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

🧲 C++ algorithm

🔍 백준 10773번 제로

#include <iostream>
#include <stack>
using namespace std;

int k, result = 0;
stack<int> stack_s;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k;
    while(k--) {
        int n;
        cin >> n;
        if(n == 0)
        stack_s.pop();
        else
        stack_s.push(n);
    }

    while(!stack_s.empty()) {
        result += stack_s.top();
        stack_s.pop();
    }
    cout << result;
}