1~3 개월의 준비 기간을 가지고 풀기에 좋은 문제들을 가지고 있는 특징이 있다.
이번 내용은 Stack + Queue + Heap주제다.
Removing Stars From a String
https://leetcode.com/problems/removing-stars-from-a-string/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string removeStars(string s) {
stack<char> charStack;
for(char& c : s){
if(c == '*'){
charStack.pop();
} else{
charStack.push(c);
}
}
string answer = "";
while(!charStack.empty()){
char c = charStack.top();
charStack.pop();
answer += c;
}
if(!answer.empty()) reverse(answer.begin(),answer.end());
return answer;
}
};
Asteroid Collision
link: https://leetcode.com/problems/asteroid-collision/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> answer;
stack<int> numStack;
bool flag = true;
for(int i = 0; i < asteroids.size(); i++){
int currRock = asteroids[i];
while(!numStack.empty() && flag){
int prevRock = numStack.top();
if(currRock < 0 && prevRock > 0){
int absCurr = abs(currRock), absPrev = abs(prevRock);
if(absCurr > absPrev){
numStack.pop();
} else{
flag = false;
if(absCurr == absPrev) numStack.pop();
break;
}
} else{
break;
}
}
numStack.push(currRock);
if(!flag) numStack.pop();
flag = true;
}
while(!numStack.empty()){
answer.push_back(numStack.top());
numStack.pop();
}
reverse(answer.begin(),answer.end());
return answer;
}
};
//개선 된 코드
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> answer;
stack<int> numStack;
bool popChance = false;
for(int& n : asteroids){
int currRock = n;
popChance = false;
while(!numStack.empty() && numStack.top() > 0 && currRock < 0){
int absCurr = abs(currRock);
int prevRock = abs(numStack.top());
if(absCurr > prevRock){
numStack.pop();
} else{
if(absCurr == prevRock){
numStack.pop();
}
popChance = true;
break;
}
}
numStack.push(currRock);
if(popChance) numStack.pop();
}
while(!numStack.empty()){
answer.push_back(numStack.top());
numStack.pop();
}
reverse(answer.begin(),answer.end());
return answer;
}
};
Decode String
link : https://leetcode.com/problems/decode-string/?envType=study-plan-v2&envId=leetcode-75
//실패
class Solution {
public:
string decodeString(string s) {
string answer = "";
stack<char> charStack;
stack<int> numStack;
bool valid = false;
string num = "";
for(int i = 0; i < s.length(); i++){
char currChar = s[i];
if(isdigit(currChar)){
//numStack.push(currChar);
//continue;
num += currChar;
continue;
}
if(currChar == '[' || currChar!= ']' && valid){
valid = true;
charStack.push(currChar);
if(!num.empty()){
numStack.push(stoi(num));
num = "";
}
} else if(currChar == ']'){
valid = false;
string tmp = "";
while(!charStack.empty() && charStack.top() != '['){
tmp += charStack.top();
charStack.pop();
}
charStack.pop();
int n = numStack.top();
numStack.pop();
string add = "";
while(n--){
add += tmp;
}
reverse(add.begin(), add.end());
for(char& c : add) charStack.push(c);
} else{
//bool flag = false;
string find = "";
while(!charStack.empty()){
//flag = true;
find += charStack.top();
charStack.pop();
}
reverse(find.begin(), find.end());
//if(flag) reverse(answer.begin(), answer.end());
answer += find;
answer += currChar;
}
}
bool check = false;
while(!charStack.empty()){
check = true;
answer += charStack.top();
charStack.pop();
}
if(check) reverse(answer.begin(), answer.end());
return answer;
}
};
//성공
class Solution {
public:
string decodeString(string s) {
stack<char> stack;
for(int i = 0; i < s.length(); i++){
char currChar = s[i];
if(currChar == ']'){
string tmp = "";
while(stack.top() != '['){
tmp += stack.top();
stack.pop();
}
stack.pop();
string numTmp = "";
while(!stack.empty() && isdigit(stack.top())){
numTmp += stack.top();
stack.pop();
}
reverse(numTmp.begin(), numTmp.end());
int num = stoi(numTmp);
string add = "";
while(num--){
add += tmp;
}
reverse(add.begin(), add.end());
for(char& c : add) stack.push(c);
} else{
stack.push(currChar);
}
}
string res;
while(!stack.empty()){
res += stack.top();
stack.pop();
}
reverse(res.begin(), res.end());
return res;
}
};Number of Recent Calls
link : https://leetcode.com/problems/number-of-recent-calls/?envType=study-plan-v2&envId=leetcode-75
class RecentCounter {
public:
queue<int> q;
RecentCounter() {
}
int ping(int t) {
int lower = t - 3000;
while(!q.empty() && lower > q.front()){
q.pop();
}
q.push(t);
return q.size();
}
};
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter* obj = new RecentCounter();
* int param_1 = obj->ping(t);
*/Dota2 Senate
link : https://leetcode.com/problems/dota2-senate/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string predictPartyVictory(string senate) {
queue<int> rq, dq;
int n = senate.size();
for(int i = 0; i < senate.size(); i++){
if(senate[i] == 'R') rq.push(i);
if(senate[i] == 'D') dq.push(i);
}
while(!rq.empty() && !dq.empty()){
int r = rq.front();
rq.pop();
int d = dq.front();
dq.pop();
if(r < d){
rq.push(r + n);
} else{
dq.push(d + n);
}
}
return rq.empty() ? "Dire" : "Radiant";
}
};
Kth Largest Element in an Array
link: https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>> pq;
for(int i = 0; i < nums.size(); i++){
pq.push(nums[i]);
}
int num = 0;
while(k--){
num = pq.top();
pq.pop();
}
return num;
}
};
Smallest Number in Infinite Set
link : https://leetcode.com/problems/smallest-number-in-infinite-set/description/?envType=study-plan-v2&envId=leetcode-75
class SmallestInfiniteSet {
public:
priority_queue<int,vector<int>, greater<int>> minq;
set<int> available;
SmallestInfiniteSet() {
for(int i = 1; i <= 1000; i++){
minq.push(i);
}
}
int popSmallest() {
int res = minq.top();
available.insert(res);
minq.pop();
return res;
}
void addBack(int num) {
if(available.contains(num)){
available.erase(num);
minq.push(num);
}
}
};
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
* int param_1 = obj->popSmallest();
* obj->addBack(num);
*/
Maximum Subsequence Score
link : https://leetcode.com/problems/maximum-subsequence-score/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int,int>> v;
int n = nums2.size();
for(int i = 0; i < n; i++){
v.push_back({nums2[i],i});
}
sort(v.rbegin(), v.rend());
long long sum = 0;
long long answer = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 0; i < v.size(); i++){
pair<int,int> p = v[i];
sum += nums1[p.second];
pq.push(nums1[p.second]);
if(pq.size() == k){
answer = max(answer, sum * p.first);
sum -= pq.top();
pq.pop();
}
}
return answer;
}
};
Total Cost to Hire K Workers
link : https://leetcode.com/problems/total-cost-to-hire-k-workers/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
long long answer = 0;
priority_queue<int, vector<int>, greater<int>> leftQ, rightQ;
int n = costs.size();
if(n >= candidates * 2){
for(int i = 0; i < candidates; i++){
leftQ.push(costs[i]);
rightQ.push(costs[n - 1 - i]);
}
} else{
for(int i = 0; i < costs.size(); i++){
leftQ.push(costs[i]);
}
}
int nextHead = candidates;
int nextTail = costs.size() - 1 - candidates;
int picked = 0;
//cout << leftQ.size() << ' ' << rightQ.size();
while(picked < k){
if(rightQ.empty() || !leftQ.empty() && leftQ.top() <= rightQ.top()){
answer += leftQ.top();
leftQ.pop();
if(nextHead <= nextTail){
leftQ.push(costs[nextHead]);
nextHead++;
}
} else{
answer += rightQ.top();
rightQ.pop();
if(nextTail >= nextHead){
rightQ.push(costs[nextTail]);
nextTail--;
}
}
picked++;
}
return answer;
}
};
복습할 문제
-
Asteroid Collision : 문제를 잘 못 읽어서 좀 헤맸고 또 스택 개념을 내가 잘 활용 못한거 같다. 다시 풀어도 괜찮을 문제.
-
Decode String : 개인적으로 좀 어렵다고 느껴진 문제다. Stack 을 여러번 사용해야 하는 점에서 어려움을 겪었는데 되게 구현적인 부분이 컸다. 꽤 좋은 연습 문제였다 생각해서 다음번에 다시 풀어봐도 좋을 거 같다.
-
Dota2 Senate : 문제가 구현에 가까웠다. 사실 문제는 요란해도 아이디어만 잘 짜면 쉬운 문제긴 하지만 아이디어가 잘 안나와서 어려웠다. 다음에 복습 용으로 다시 풀때는 내 방법으로 구현을 해보자.
-
Maximum Subsequence Score : Priority Queue 를 활용할 수 있는 아이디어를 구상하기 까지 좀 어려웠다. 다시 풀어도 할 수 있을지 의문이긴 하지만 해봐야지.
-
Total Cost to Hire K workers : 와우.. 솔직히 어려웠다. Left 와 Right 을 유지해야 한다니. 되게 그리디한 문제고 다시 풀어도 힘들거 같다.
