Premium Algo 주제인 Stack + Queue + Heap 이다.
Tenary Expression Parser
link : https://leetcode.com/problems/ternary-expression-parser/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
string parseTernary(string expression) {
stack<char> charStack;
for(int i = expression.size()-1; i >= 0;){
char curr = expression[i];
if(curr == '?'){
//do something
char op = expression[i-1];
char first = charStack.top();
charStack.pop();
char second = charStack.top();
charStack.pop();
if(op == 'T'){
charStack.push(first);
} else{
charStack.push(second);
}
i -=2;
} else{
if(isalpha(curr) || isdigit(curr)) charStack.push(curr);
i--;
}
}
return string(1,charStack.top());
}
};
Find Permutation
link : https://leetcode.com/problems/find-permutation/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> answer;
int cnt = 1;
stack<int> stack;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'I'){
answer.push_back(cnt++);
while(!stack.empty()){
answer.push_back(stack.top());
stack.pop();
}
} else{
stack.push(cnt++);
}
}
answer.push_back(cnt);
while(!stack.empty()){
answer.push_back(stack.top());
stack.pop();
}
return answer;
}
};Moving Average from Data Stream
link : https://leetcode.com/problems/moving-average-from-data-stream/description/?envType=study-plan-v2&envId=premium-algo-100
class MovingAverage {
public:
queue<int> q;
int limit = 0;
int lastSum = 0;
MovingAverage(int size) {
limit = size;
}
double next(int val) {
if(!q.empty() && q.size() == limit){
lastSum -= q.front();
q.pop();
}
lastSum += val;
q.push(val);
return (double) lastSum / q.size();
}
};
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage* obj = new MovingAverage(size);
* double param_1 = obj->next(val);
*/
First Unique Number
link : https://leetcode.com/problems/first-unique-number/?envType=study-plan-v2&envId=premium-algo-100
class FirstUnique {
public:
map<int,int> hashMap;
queue<int> q;
FirstUnique(vector<int>& nums) {
for(int& n : nums){
hashMap[n]++;
q.push(n);
}
}
int showFirstUnique() {
while(!q.empty() && hashMap[q.front()] > 1){
//hashMap[q.front()]--;
q.pop();
}
if(q.empty()) return -1;
int ret = q.front();
return ret;
}
void add(int value) {
hashMap[value]++;
q.push(value);
}
};
/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique* obj = new FirstUnique(nums);
* int param_1 = obj->showFirstUnique();
* obj->add(value);
*/
High Five
link : https://leetcode.com/problems/high-five/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
vector<vector<int>> answer;
priority_queue<int, vector<int>> pq;
sort(items.begin(), items.end());
int id = items[0][0];
int sum = 0;
for(int i = 0; i < items.size(); i++){
if(items[i][0] != id){
int cnt = 0;
while(!pq.empty()){
cnt++;
sum += pq.top();
if(cnt == 5) answer.push_back({id, sum / 5});
pq.pop();
}
id = items[i][0];
sum = 0;
pq.push(items[i][1]);
} else{
pq.push(items[i][1]);
}
}
if(!pq.empty()){
int cnt = 0;
//cout << pq.size();
while(!pq.empty()){
cnt++;
sum += pq.top();
if(cnt == 5) answer.push_back({id, sum / 5});
pq.pop();
}
}
return answer;
}
};
Minimum Cost to Connect Sticks
link : https://leetcode.com/problems/minimum-cost-to-connect-sticks/description/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
int connectSticks(vector<int>& sticks) {
int answer = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for(int n : sticks) pq.push(n);
while(pq.size() > 1){
int x= pq.top();
pq.pop();
int y = pq.top();
pq.pop();
answer += x + y;
pq.push(x + y);
}
//answer += pq.top();
return answer;
}
};
Campus Bikes
link : https://leetcode.com/problems/campus-bikes/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
int findDistance(vector<int>& worker, vector<int>& bike){
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1]);
}
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
vector<tuple<int,int,int>> allTriplets;
for(int worker = 0; worker < workers.size(); worker++){
for(int bike = 0; bike < bikes.size(); bike++){
int distance = findDistance(workers[worker], bikes[bike]);
allTriplets.push_back({distance, worker, bike});
}
}
sort(allTriplets.begin(), allTriplets.end());
vector<int> bikeStatus(bikes.size(), false);
vector<int> workerStatus(workers.size(), -1);
int pairCount = 0;
for(auto[dist, worker, bike] : allTriplets){
if(workerStatus[worker] == -1 && !bikeStatus[bike]){
bikeStatus[bike] = true;
workerStatus[worker] = bike;
pairCount++;
if(pairCount == workers.size()){
return workerStatus;
}
}
}
return workerStatus;
}
};
Rearrange String k Distance Apart
link : https://leetcode.com/problems/rearrange-string-k-distance-apart/?envType=study-plan-v2&envId=premium-algo-100
class Solution {
public:
string rearrangeString(string s, int k) {
map<char,int> hashMap;
priority_queue<pair<int,char>> pq;
for(int i = 0; i < s.size(); i++){
hashMap[s[i]]++;
}
for(auto& it : hashMap){
pq.push({it.second, it.first});
}
string answer;
queue<pair<int,char>> wait;
while(answer.size() != s.size()){
int index = answer.size();
if(!wait.empty() && (index - wait.front().first) >= k){
auto q = wait.front(); wait.pop();
pq.push({hashMap[q.second], q.second});
}
if(pq.empty()){
return "";
}
char currChar = pq.top().second; pq.pop();
answer += currChar;
hashMap[currChar]--;
if(hashMap[currChar] > 0){
wait.push({index, currChar}) ;
}
}
return answer;
}
};
복습 필요한 문제
-
Find Permutation : 처음 문제를 읽고.. Stack 을 활용하는 문제라는 생각을 전혀 못해서 어떻게 활용할지 몰라서 결국에는 풀이를 참고했다. 대체 어떻게 이런 풀이가 나오지?? 했는데 Stack 활용을 더 깊게 고민하면 나올 수 있는 풀이였다.
-
Campus Bikes : 분명 개념은 알았는데 다시 풀어볼려니 또 헷갈렸다. 복습해도 좋은 문제같다.
-
Rearrange String k Distance Apart : 솔직히 아이디어는 가지고 있었는데 답변을 보고 참고했다. 다시 풀어보면 좋을거 같다.
