이번 포스트에서는 Sliding Window와 관련된 문제를 풀어보겠습니다.
풀이는 코드에 직접 적었습니다.
혹시나 궁금하신 부분이 있으시면 댓글로 문의 부탁드립니다.
1. Best Time to Buy and Sell Stock
풀이
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 이전에 나온 최솟값을 저장하는 변수를 정의합니다.
// 최솟값에 사서 현재값이 팔면 이익이 나오는데 그 이익의 최대를 구하면 됩니다.
int ans = 0, min_value = prices[0];
// 배열의 길이가 최소 1이기 때문에 1부터 시작하실 수 있습니다.
for (int i = 1; i < (int)prices.size(); ++i) {
// 이전의 최솟값에 사서, 현재값이 팔아 이익을 구하고, 그 값을 최댓값과 비교합니다.
ans = max(ans, prices[i] - min_value);
// 최솟값을 업데이트합니다.
min_value = min(min_value, prices[i]);
}
return ans;
}
};
2. Longest Substring Without Repeating Characters
풀이
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int n = (int)s.length();
// substring의 시작을 가리키는 포인터를 정의합니다.
int start = 0;
// substring에 들어있는 문자 중복을 체크하기 위해서 해시맵을 정의합니다.
unordered_map<char, int> count;
int ans = 0;
for (int i = 0; i < n; ++i) {
// 현재 문자를 substring에 추가합니다.
count[s[i]]++;
// 만약 현재의 알파벳이 이전에 나왔으면
// 그 알파벳이 사라질때까지 시작 포인터를 움직여서 substring에서 제외시킵니다.
while(count[s[i]] > 1) {
count[s[start]]--;
start++;
}
// substring의 길이와 최댓값을 비교합니다.
ans = max(ans, i - start + 1);
}
return ans;
}
};
3. Longest Repeating Character Replacement
풀이
class Solution {
public:
bool valid(vector<int> & count, int k) {
// 최빈값과 전체 길이를 구합니다.
int max_val = 0;
int total = 0;
for (auto &x:count) {
max_val = max(max_val, x);
total += x;
}
// 최빈값을 제외한 문자의 개수가 K보다 작거나 같으면 true, 아니면 false 입니다.
return total - max_val <= k;
}
int characterReplacement(string s, int k) {
// Sliding window 안에 들어있는 문자의 수를 저장하기 위한 배열을 정의합니다.
vector<int> count(26, 0);
// Substring의 시작지점을 가리키는 변수를 지정합니다.
int start = 0, ans = 0;
// 배열을 순회하면서 가장 자주 나온 문자열을 제외한 문자들의 수가 K보다 작은지를 확인합니다.
// 만약 크다면, start를 옮겨서 Substring 길이를 줄여야 합니다.
for (int i = 0; i < (int)s.length(); ++i) {
count[s[i] - 'A']++;
// valid() 함수는 K번으로 바꿀 수 있는지 확인합니다.
if (!valid(count, k)) {
count[s[start]-'A']--;
start++;
}
// 반드시 valid한 경우만 나오기 때문에, 최댓값을 바로 비교하면 됩니다.
ans = max(ans, i - start + 1);
}
return ans;
}
};
4. Minimum Window Substring
풀이
class Solution {
public:
bool canReduce(vector<vector<int>> & count, vector<vector<int>> & target_count, char & c) {
// 만약 start 문자가 t에 있는 수보다 크면 불필요한 값이므로 줄일 수 있습니다.
if (c >= 'A' && c <='Z') {
if (count[0][c -'A'] > target_count[0][c-'A']) {
return true;
}
} else {
if (count[1][c -'a'] > target_count[1][c-'a']) {
return true;
}
}
return false;
}
bool valid(vector<vector<int>> & count, vector<vector<int>> & target_count) {
// 두 배열을 비교해야 하는데, target_count를 기준으로 비교합니다.
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 26; ++j) {
// target_count의 값이 0인 것은 고려할 필요가 없습니다.
// 왜냐하면 target_count에 있는 문자구성만 들어있으면 되고,
// 그 외 문자는 언제든 들어갈 수 있기 때문입니다.
if (target_count[i][j] > 0 && target_count[i][j] > count[i][j]) {
return false;
}
}
}
return true;
}
string minWindow(string s, string t) {
// t에 들어있는 문자구성을 저장합니다.
vector<vector<int>> target_count(2, vector<int> (26, 0));
for (auto &x:t) {
// uppercase는 [0] 번째에 저장합니다.
if (x >= 'A' && x <= 'Z') {
target_count[0][x - 'A']++;
}
// lowercase는 [1] 번째에 저장합니다.
else {
target_count[1][x - 'a']++;
}
}
int start = 0, min_val = 1e9;
string ans = "";
// substring에 들어갈 문자구성을 저장하는 배열을 생성합니다.
vector<vector<int>> count(2, vector<int>(26, 0));
for (int i = 0; i < (int)s.length(); ++i) {
// 현재 문자를 배열에 저장합니다. -> 윈도우를 증가합니다.
if (s[i] >= 'A' && s[i] <= 'Z') {
count[0][s[i]-'A']++;
} else {
count[1][s[i]-'a']++;
}
// 줄일 수 있는지 체크합니다.
while(start < i && canReduce(count, target_count, s[start])) {
if (s[start] >= 'A' & s[start] <= 'Z') {
count[0][s[start] - 'A']--;
} else {
count[1][s[start] - 'a']--;
}
start++;
}
// valid한지 확인합니다.
if (valid(count, target_count) && min_val > i - start + 1) {
min_val = i - start + 1;
ans = s.substr(start, i - start + 1);
}
}
return ans;
}
};
Sliding Window 문제는 전반적으로 Two pointers와 비슷한 느낌이 있습니다. 하지만 다른 점은 Sliding Window의 경우 시작과 끝의 사이값들을 모두 tracking하는 경우가 많습니다. 그래서 주로 조건에 맞는 subarray 또는 substring을 구할 때 자주 사용합니다. 문제를 풀 때 Sliding Window를 사용해야겠다는 생각이 드셨다면, 어떤 조건에서 Window를 조절할지 고민해보시는 것이 좋습니다.
Sliding Window와 비슷한 Two pointers 패턴 문제들도 한 번 풀어보시기 바랍니다 :)
Best Time to Buy and Sell Stock 시리즈 문제를 더 풀어보고 싶으신 분들은 아래 포스트도 한 번 보시는 것을 추천드립니다.
'개발자 컨닝노트 > Leetcode 대표 문제 정복하기' 카테고리의 다른 글
Stack 대표 문제 풀기 (1) | 2022.11.01 |
---|---|
Best Time to Buy and Sell Stock (0) | 2022.11.01 |
Two pointers 대표 문제 풀기 (0) | 2022.10.31 |
배열과 해시 대표 문제 풀기 (0) | 2022.10.30 |
Two Sum (0) | 2022.10.23 |
댓글