문제 1: 최소값 스택
push, pop, top 연산을 지원하면서도 상수 시간 내에 최소 요소를 검색할 수 있는 스택을 설계하세요.
MinStack 클래스를 구현해야 합니다:
- MinStack(): 스택 객체 초기화
- void push(int val): 요소를 스택에 삽입
- void pop(): 스택 상단 요소 삭제
- int top(): 스택 상단 요소 반환
- int getMin(): 스택의 최소 요소 반환, 시간 복잡도 O(1)
풀이思路
두 개의 스택을 사용합니다. 하나는 데이터를 저장하고, 다른 하나는 각 요소 삽입 시점에서의 최소값을 저장합니다.
class MinStack {
private:
std::stack<int> dataStack;
std::stack<int> minStack;
public:
MinStack() {
}
void push(int val) {
dataStack.push(val);
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}
void pop() {
if (dataStack.empty()) return;
if (dataStack.top() == minStack.top()) {
minStack.pop();
}
dataStack.pop();
}
int top() {
return dataStack.top();
}
int getMin() {
return minStack.top();
}
};문제 2: 스택의 push/弹出 순서 검증
두 개의 정수 배열이 주어집니다. 첫 번째 배열은 스택의 푸시 순서를 나타내고, 두 번째 배열이 해당 스택의 팝 순서인지 판단하세요.
푸시되는 모든 숫자는 서로 다릅니다. 예를 들어, 1,2,3,4,5가 푸시 순서라면 4,5,3,2,1은 유효한 팝 순서이지만, 4,3,5,1,2는 유효하지 않습니다.
解题思路
푸시 순서를 시뮬레이션하면서 팝 순서와 매칭되는지 확인합니다. 매칭되면 스택에서 팝하고, 그렇지 않으면 계속 푸시합니다.
class Solution {
public:
bool IsPopOrder(std::vector<int>& pushSeq, std::vector<int>& popSeq) {
std::stack<int> st;
int pushIdx = 0;
int popIdx = 0;
while (pushIdx < pushSeq.size()) {
st.push(pushSeq[pushIdx++]);
while (!st.empty() && st.top() == popSeq[popIdx]) {
st.pop();
++popIdx;
}
}
return st.empty();
}
};문제 3: 역폴란드 표기법 계산
문자열 배열 tokens가 주어지는데, 이는 역폴란드 표기법으로 표현된 산술 표현식입니다. 해당 표현식을 계산하여 값을 반환하세요.
유효한 연산자는 +, -, *, /입니다. 각 피연산자는 정수이거나 다른 표현식일 수 있습니다. 나눗셈은 0으로 향하도록 자릅니다.
예시:
- 중위 표기: 2 + 1 * 3
- 후위 표기: 2 1 3 * +
解题思路
후위 표기법을 계산할 때 피연산자는 스택에 푸시하고, 연산자를 만나면 스택 상단 두 요소를 꺼내 연산합니다.
class Solution {
public:
int evalRPN(std::vector<std::string>& tokens) {
std::stack<long long> st;
for (const auto& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
long long first = st.top();
st.pop();
long long second = st.top();
st.pop();
switch (token[0]) {
case '+':
st.push(second + first);
break;
case '-':
st.push(second - first);
break;
case '*':
st.push(second * first);
break;
case '/':
st.push(second / first);
break;
}
} else {
st.push(std::stoi(token));
}
}
return static_cast<int>(st.top());
}
};문제 4: 두 스택으로 큐 구현
두 개의 스택만 사용하여 FIFO 큐를 구현하세요. 다음 연산을 지원해야 합니다: push, pop, peek, empty
解题思路
두 개의 스택을 사용합니다. 하나는 입력용이고 다른 하나는 출력용입니다. 출력 스택이 비어있으면 입력 스택의 모든 요소를 출력 스택으로 이동시킵니다.
class MyQueue {
private:
std::stack<int> inputStack;
std::stack<int> outputStack;
void transferElements() {
while (!inputStack.empty()) {
outputStack.push(inputStack.top());
inputStack.pop();
}
}
public:
MyQueue() {
}
void push(int x) {
inputStack.push(x);
}
int pop() {
if (!outputStack.empty()) {
int val = outputStack.top();
outputStack.pop();
return val;
}
if (inputStack.empty()) {
return -1;
}
transferElements();
int val = outputStack.top();
outputStack.pop();
return val;
}
int peek() {
if (!outputStack.empty()) {
return outputStack.top();
}
if (inputStack.empty()) {
return -1;
}
transferElements();
return outputStack.top();
}
bool empty() {
return inputStack.empty() && outputStack.empty();
}
};문제 5: 이진 트리 레벨 순회
이진 트리의 루트 노드가 주어질 때, 노드 값을 레벨 순서로 반환하세요 (층별로, 왼쪽에서 오른쪽으로).
解题思路
큐를 사용하여 BFS 방식으로 순회합니다. 각 레벨의 노드 수를 추적하여 층별로 결과를 저장합니다.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};
class Solution {
public:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
size_t levelSize = q.size();
std::vector<int> currentLevel;
for (size_t i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
return result;
}
};문제 6: 역순 레벨 순회
이진 트리의 루트 노드가 주어질 때, 노드 값을 아래에서 위로 레벨 순서로 반환하세요 (나무의 가장 아래층부터 루트층까지, 왼쪽에서 오른쪽).
解题思路
기본 레벨 순회를 수행한 후 결과 배열을 뒤집으면 됩니다.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};
class Solution {
public:
std::vector<std::vector<int>> levelOrderBottom(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
size_t levelSize = q.size();
std::vector<int> currentLevel;
for (size_t i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
std::reverse(result.begin(), result.end());
return result;
}
};