[Algorithm] ์ฌ๋ผ์ด๋ฉ ์๋์ฐ Sliding Window ์๊ณ ๋ฆฌ์ฆ ํบ์๋ณด๊ธฐ
์ฌ๋ผ์ด๋ฉ ์๋์ฐ ์๊ณ ๋ฆฌ์ฆ ๊ฐ๋
์ฌ๋ผ์ด๋ฉ ์๋์ฐ ์๊ณ ๋ฆฌ์ฆ(Sliding Window Algorithm)์ ๋ฐฐ์ด๊ณผ ๊ฐ์ ์ ํ ์๋ฃ๊ตฌ์กฐ์์ ์ฐ์๋ ๊ตฌ๊ฐ ๋ด์ ๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ์ฒ๋ฆฌํ๊ธฐ ์ํด ์ฌ์ฉํ๋ ๊ธฐ๋ฒ์ด๋ค. ํนํ ๋ฐฐ์ด ๋ด ์ฐ์๋ ์์์ ํฉ, ์ต๋๊ฐ, ์ต์๊ฐ ๋ฑ์ ๊ณ์ฐํ ๋ ์ ์ฉํ๋ค.
์ฌ๋ผ์ด๋ฉ ์๋์ฐ๋ ์ด๋ฆ ๊ทธ๋๋ก ๊ณ ์ /๊ฐ๋ณ ํฌ๊ธฐ์ ๋ฒ์(์๋์ฐ)๋ฅผ ์ด๋(์ฌ๋ผ์ด๋) ์ํค๋ฉด์ ํ์ํ ๊ณ์ฐ์ ๋ฐ๋ณตํ๋ ๋ฐฉ์์ด๋ค. ์ด๋ ์ ์ฒด ๋ฐฐ์ด์ ํ ๋ฒ๋ง ์ํํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ ์ค๋ณต ์ฐ์ฐ์ ํผํ๊ณ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ ํ ์ ์๋ค. ์ผ๋ฐ์ ์ผ๋ก ์ฌ๋ผ์ด๋ฉ ์๋์ฐ ๊ธฐ๋ฒ์ ์ฌ์ฉํ๋ฉด O(n)์ ์๊ฐ ๋ณต์ก๋๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
// ์ฃผ์ด์ง ๋ฐฐ์ด์์ ์ฐ์๋ k๊ฐ ์์์ ์ต๋ ํฉ์ ์ฐพ๋ ํจ์
function maxSumSubarray(arr, k) {
let maxSum = 0;
let windowSum = 0;
// ์ด๊ธฐ ์๋์ฐ(k๊ฐ์ ์์) ํฉ ๊ณ์ฐ
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// ์ฌ๋ผ์ด๋ฉ ์๋์ฐ ์ด๋
for (let end = k; end < arr.length; end++) {
const start = end - k;
// arr[end]๊ฐ ์๋ก ์ถ๊ฐ๋๋ ์์ ์ด๋ฏ๋ก arr[end] - arr[start] ์์๋ก ๊ณ์ฐ
windowSum += arr[end] - arr[start];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
const result = maxSumSubarray([2, 1, 5, 1, 3, 2], 3);
console.log(result); // 9
์ ์์๋ ์ฌ๋ผ์ด๋ฉ ์๋์ฐ ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ๋ฐฐ์ด ๋ด ์ฐ์๋ k๊ฐ ์์์ ์ต๋ ํฉ์ ์ฐพ๋ ํจ์๋ค. ์๋ฅผ ๋ค์ด ์ด๊ธฐ ๋ฐฐ์ด [2, 1, 5, 1, 3, 2]
์์ ์ฒ์ 3๊ฐ ์์์ ํฉ์ 2 + 1 + 5 = 8
์ด๋ค. ์ดํ ์๋์ฐ๋ฅผ ํ ์นธ์ฉ ์ด๋ํ๋ฉด์ k๊ฐ์ ์์๋ฅผ ๋ํด ๋๊ฐ๋ค.
- (215)132 → 2 + 1 + 5 = 8
- 2(151)32 → 1 + 5 + 1 = 7
- 21(513)2 → 5 + 1 + 3 = 9 (์ต๋๊ฐ)
- 215(132) → 1 + 3 + 2 = 6
ํํธ ๋งค๋ฒ ์๋์ฐ์ ์๋ ๋ชจ๋ k
๊ฐ ์์๋ฅผ ๋ฐ๋ณตํด์ ๋ํ ํ์ ์์ด, ์ด์ ์๋์ฐ์์ ๊ณ์ฐํ ๊ฐ์, ์๋ก ์ถ๊ฐํ ์์์ ์ ๊ฑฐํ ์์๋ฅผ ๋ฐ์ํ๋ฉด ํฉ๊ณ๋ฅผ ๋ ํจ์จ์ ์ผ๋ก ์
๋ฐ์ดํธํ ์ ์๋ค. ์ด์ ์๋์ฐ ๊ณ์ฐ๊ฐ + (์ถ๊ฐํ๋ ์์ - ๋น ์ง๋ ์์)
์๊ฐ์ ์ผ๋ก ํํํด ๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
์ฌ๋ผ์ด๋ฉ ์๋์ฐ ์๊ณ ๋ฆฌ์ฆ ํ์ฉ
ํ๋ก๊ทธ๋๋จธ์ค ๋ ๋ฒจ 2 - ํ ์ธํ์ฌ ๋ฌธ์ (131127)๋ ์ฌ๋ผ์ด๋ฉ ์๋์ฐ ๊ธฐ๋ฒ์ ํ์ฉํ ์ ์๋ค. ์ฃผ์ด์ง ํ ์ธ ๋ชฉ๋ก(discount)์์ 10์ผ ์ฐ์ ๊ตฌ๊ฐ์ ํฌํจ๋์ด ์๋ ์ ํ/์๋๊ณผ, ๊ตฌ๋งคํ๊ณ ์ถ์ ์ ํ/์๋์ด ์ ํํ ์ผ์นํ๋ ๊ฒฝ์ฐ์ ์ด๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ค.
- want: ๊ตฌ๋งค ์ ํ ๋ชฉ๋ก (๋ฐฐ์ด)
- number: ๊ตฌ๋งค ์ ํ ์๋ (๋ฐฐ์ด, want ๋ฐฐ์ด ์ธ๋ฑ์ค์ ๋งคํ)
- discount : ํ ์ธ ์ ํ ๋ชฉ๋ก (๋ฐฐ์ด, ๊ฐ ์ธ๋ฑ์ค๋ ๋ ์ง๋ฅผ ๊ฐ๋ฆฌํด)
๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ค๋ฉด discount ๋ฐฐ์ด์ 0๋ฒ ์ธ๋ฑ์ค๋ถํฐ ์ํํ๋ฉด์, ํด๋น ์์น์์ ์์ํ๋ 10์ผ ๊ตฌ๊ฐ์ ํ ์ธ ์ ํ/์๋์ด, ๊ตฌ๋งค ์ ํ/์๋๊ณผ ์ผ์นํ๋์ง ์ฌ๋ถ๋ฅผ ํ์ธํ๋ฉด ๋๋ค.
์ด๋ 10์ผ ๊ตฌ๊ฐ์ ๋ชจ๋ ์ ํ ์๋์ ๋งค๋ฒ ๊ณ์ฐํ ํ์ ์์ด, ์ด์ ๊ตฌ๊ฐ์์ ๊ณ์ฐํ ์๋์ฐ ์ ๋ณด์ ์ถ๊ฐ/์ ๊ฑฐ๋๋ ์ ํ์ ์๋๋ง ์กฐ์ ํ๋ ๋ฐฉ์์ผ๋ก ๋ถํ์ํ ์ฐ์ฐ์ ์ค์ผ ์ ์๋ค.
const WINDOW_SIZE = 10;
function solution(want, number, discount) {
const wantMap = want.reduce((map, item, i) => map.set(item, number[i]), new Map());
const windowMap = new Map();
let count = 0;
// ์ด๊ธฐ ์๋์ฐ ์ค์ (์ฒซ 10์ผ)
// chicken => 1, apple => 3, banana => 2, rice => 2, pork => 2
for (let i = 0; i < WINDOW_SIZE; i++) {
windowMap.set(discount[i], (windowMap.get(discount[i]) ?? 0) + 1);
}
// ํ์ฌ ์๋์ฐ๊ฐ ์กฐ๊ฑด์ ๋ง์กฑํ๋์ง ํ์ธ
const checkIfValid = () => {
for (const [item, qty] of wantMap.entries()) {
if ((windowMap.get(item) ?? 0) < qty) return false;
}
return true;
};
// ์ฒซ 10์ผ ์ฒดํฌ
if (checkIfValid()) count++;
// ์ฌ๋ผ์ด๋ฉ ์๋์ฐ๋ก ํ์
for (let i = WINDOW_SIZE; i < discount.length; i++) {
const oldItem = discount[i - WINDOW_SIZE]; // ์ด์ ํญ๋ชฉ ์ ๊ฑฐ
const newItem = discount[i]; // ์๋ก ์ถ๊ฐ๋ ํญ๋ชฉ ์ถ๊ฐ
// ์๋์ฐ ์
๋ฐ์ดํธ
// i10 = chicken => 1, apple => 3, banana => 2, rice => 2, pork => 2
// i11 = chicken => 0, apple => 3, banana => 2, rice => 2, pork => 2, pot => 1
// i12 = chicken => 0, apple => 2, banana => 3, rice => 2, pork => 2, pot => 1
// ...
windowMap.set(oldItem, windowMap.get(oldItem) - 1);
windowMap.set(newItem, (windowMap.get(newItem) ?? 0) + 1);
// ์กฐ๊ฑด ๋ง์กฑ ์ฌ๋ถ ์ฒดํฌ
if (checkIfValid()) count++;
}
return count;
}
const want = ["banana", "apple", "rice", "pork", "pot"];
const number = [3, 2, 2, 2, 1];
const discount = [
"chicken",
"apple",
"apple",
"banana",
"rice",
"apple",
"pork",
"banana",
"pork",
"rice",
"pot",
"banana",
"apple",
"banana",
];
const result = solution(want, number, discount);
console.log(result); // 3
- ๊ตฌ๋งคํด์ผ ํ๋ ์ ํ ๋ชฉ๋ก/์๋์ ๋งคํํ Map ์์ฑ (wantMap)
- ์ด๊ธฐ ์๋์ฐ Map ์์ฑ (windowMap)
- ์ฌ๋ผ์ด๋ฉ ์๋์ฐ๋ก discount ๋ฐฐ์ด ํ์ ๋ฐ windowMap ์ ๋ฐ์ดํธ
- ์ ๋ฐ์ดํธํ windowMap๊ณผ wantMap ๋น๊ต
์ ๊ณผ์ ์ ์๊ฐ์ ์ผ๋ก ํํํด ๋ณด๋ฉด ์๋์ ๊ฐ๋ค.
๊ธ ์์ ์ฌํญ์ ๋ ธ์ ํ์ด์ง์ ๊ฐ์ฅ ๋น ๋ฅด๊ฒ ๋ฐ์๋ฉ๋๋ค. ๋งํฌ๋ฅผ ์ฐธ๊ณ ํด ์ฃผ์ธ์
'๐ช Programming' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JS] ์๋ฐ์คํฌ๋ฆฝํธ ์ฝ๋ ์ต์ ํ ๊ธฐ๋ฒ ๋ชจ์ (18) | 2024.12.07 |
---|---|
[React] ๋ฆฌ์กํธ ์ฝ๋๋ฅผ ๊ฐ์ ํ ์ ์๋ 4๊ฐ์ง ํ (0) | 2024.10.28 |
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 2 (1) | 2024.10.13 |
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 1 (0) | 2024.10.05 |
[TS] ํ์ ์คํฌ๋ฆฝํธ ๋ธ๋๋๋ ํ์ (0) | 2024.09.26 |
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋ค๋ฅธ ๊ธ
-
[JS] ์๋ฐ์คํฌ๋ฆฝํธ ์ฝ๋ ์ต์ ํ ๊ธฐ๋ฒ ๋ชจ์
[JS] ์๋ฐ์คํฌ๋ฆฝํธ ์ฝ๋ ์ต์ ํ ๊ธฐ๋ฒ ๋ชจ์
2024.12.07 -
[React] ๋ฆฌ์กํธ ์ฝ๋๋ฅผ ๊ฐ์ ํ ์ ์๋ 4๊ฐ์ง ํ
[React] ๋ฆฌ์กํธ ์ฝ๋๋ฅผ ๊ฐ์ ํ ์ ์๋ 4๊ฐ์ง ํ
2024.10.28 -
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 2
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 2
2024.10.13 -
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 1
[Flutter] ํ๋ฌํฐ ๊ธฐ์ด ๋ด์ฉ ์ ๋ฆฌ - Part 1
2024.10.05