1~3 개월의 준비 기간을 가지고 풀기에 좋은 문제들을 가지고 있는 특징이 있다.
이번 내용은 Array/String 주제다.
Merge Strings Alternately (easy)
link: https://leetcode.com/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string mergeAlternately(string word1, string word2) {
int min_length = min(word1.length(), word2.length());
bool diff = false;
string tail = "", answer = "";
if(word1.length() < word2.length()){
tail = word2;
} else if(word1.length() > word2.length()){
tail = word1;
}
for(int i = 0; i < min_length; i++){
answer += word1[i];
answer += word2[i];
}
if(!tail.empty()){
answer += tail.substr(min_length);
}
return answer;
}
};Greatest Common Divisor of Strings(easy)
link: https://leetcode.com/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
// Check if they have non-zero GCD string.
if (str1 + str2 != str2 + str1) {
return "";
}
// Get the GCD of the two lengths.
int gcdLength = gcd(str1.size(), str2.size());
return str1.substr(0, gcdLength);
}
};Kids With the Greatest Number of Candies
link: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
int max_ = *max_element(candies.begin(),candies.end());
vector<bool> answer(candies.size(), false);
for(int i = 0; i < candies.size(); i++){
if(candies[i] + extraCandies >= max_){
answer[i] = true;
}
}
return answer;
}
};Can Place Flowers
link: https://leetcode.com/problems/can-place-flowers/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if(flowerbed.size() == 1){
if(flowerbed[0] == 0) n--;
return n > 0 ? false : true;
}
if(flowerbed[0] == 0 && flowerbed[1] == 0){
flowerbed[0] = 1;
n--;
}
if(flowerbed[flowerbed.size()-1] == 0 && flowerbed[flowerbed.size()-2] == 0){
flowerbed[flowerbed.size()-1] = 1;
n--;
}
for(int i = 1; i < flowerbed.size()-1; i++){
if(flowerbed[i] == 0 && flowerbed[i-1] != 1 && flowerbed[i+1] != 1){
n--;
flowerbed[i] = 1;
if(n == 0) return true;
}
}
return n > 0 ? false : true;
}
};개선 코드
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0;
for (int i = 0; i < flowerbed.size(); i++) {
// Check if the current plot is empty.
if (flowerbed[i] == 0) {
// Check if the left and right plots are empty.
bool emptyLeftPlot = (i == 0) || (flowerbed[i - 1] == 0);
bool emptyRightPlot = (i == flowerbed.size() - 1) || (flowerbed[i + 1] == 0);
// If both plots are empty, we can plant a flower here.
if (emptyLeftPlot && emptyRightPlot) {
flowerbed[i] = 1;
count++;
if (count >= n) {
return true;
}
}
}
}
return count >= n;
}
};Reverse Vowels of a String
link: https://leetcode.com/problems/reverse-vowels-of-a-string/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string reverseVowels(string s) {
int start = 0, end = s.length()-1;
map<char,int> hashMap = {{'a',1}, {'e',1}, {'o',1}, {'u',1}, {'i',1}};
while(start < end){
bool a = hashMap.count(tolower(s[start]));
bool b = hashMap.count(tolower(s[end]));
if(a && b){
swap(s[start], s[end]);
start++;
end--;
} else if(!a && !b){
start++;
end--;
} else if(a && !b){
end--;
} else{
start++;
}
}
return s;
}
};Reverse Words in a String
link: https://leetcode.com/problems/reverse-words-in-a-string/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
string reverseWords(string s) {
stringstream ss(s);
vector<string> v;
string tmp;
while(ss >> tmp){
v.push_back(tmp);
}
reverse(v.begin(), v.end());
string answer = "";
for(string& s : v){
answer += s + " ";
}
answer.pop_back();
return answer;
}
};Product of Array Except Self
link: https://leetcode.com/problems/product-of-array-except-self/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> answer(nums.size(), 0);
answer[0] = 1;
for(int i = 1; i < nums.size(); i++){
answer[i] += answer[i-1] * nums[i-1];
}
int suffix = 1;
for(int i = nums.size()-1; i >= 0; i--){
answer[i] = suffix * answer[i];
suffix *= nums[i];
}
return answer;
}
};
Increasing Triplet Subsequence
link: https://leetcode.com/problems/increasing-triplet-subsequence/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int choice1 = INT_MAX, choice2 = INT_MAX;
for(int i = 0; i < nums.size(); i++){
if(nums[i] <= choice1) choice1 = nums[i];
else if(nums[i] <= choice2) choice2 = nums[i];
else return true;
}
return false;
}
};String Compression
link: https://leetcode.com/problems/string-compression/
class Solution {
public:
int compress(vector<char>& chars) {
string res = "";
int left = 0, right = 0;
char currChar = chars[0], nextChar = chars[0];
while(right < chars.size()){
nextChar = chars[right];
if(nextChar != currChar){
res += currChar;
if(right - left > 1) res += to_string(right - left);
currChar = nextChar;
left = right;
}
right++;
}
res += chars[left];
if(right - left > 1) res += to_string(right - left);
for(int i = 0; i < res.length(); i++){
chars[i] = res[i];
}
return res.length();
}
};복습 필요한 문제
-
Product of Array Except Self : Prefix Sum을 알아야 하는 문제인데 생각보다 까다로워서 놀랐다. 내가 많이 까먹은 잘못도 있지만 강의를 한번 보고 나서야 풀 수 있었다.
-
String Compression : 예전에 풀었던 카카오 기출 문제가 생각이 났다. 그때는 Brute Force 로 풀었는데 이번 문제는 two pointer 로 풀었고, 답을 구했음에도 좀 헤매서 다시 풀어봐야 할 것 같다.
