728x90
๋ฐ์ํ
๐ ๋ฌธ์
N๊ฐ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ฃผ์ด์ง๋ค. ์ด ์์ด์์ ์ฐ์ ๋ถ๋ถ ์์ด์ ํฉ์ด ํน์ ์ซ์ M์ด ๋๋ ๊ฒฝ์ฐ๊ฐ ๋ช ๋ฒ ์๋์ง ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
๋ง์ฝ N=8, M=6์ด๊ณ ์์ด์ด ๋ค์๊ณผ ๊ฐ๋ค๋ฉด 1 2 1 3 1 1 1 2
ํฉ์ด 6์ด ๋๋ ์ฐ์ ๋ถ๋ถ ์์ด์ {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}๋ก ์ด 3๊ฐ์ง์ด๋ค.
๐ ํ์ด
๐ง๐ป๐ป ๋์ ํ์ด ๋ฐฉ๋ฒ
- lt(์ผ์ชฝ์ ๋ด๋นํ ํฌ์ธํฐ), rt(์ค๋ฅธ์ชฝ์ ๋ด๋นํ ํฌ์ธํฐ)๋ฅผ ์ธ๋ฑ์ค 0์ผ๋ก ์ด๊ธฐํํ๋ค.
- rt ํฌ์ธํฐ๋ฅผ ํ์นธ์ฉ ์ด๋(์ฆ๊ฐ)์ํค๋ฉด์ ํฌ์ธํฐ์ ํด๋นํ๋ ๊ฐ์ sum์ ๋์ ์ํจ๋ค.
- ์ ๊ณผ์ ์์ sum์ด m๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ผ๋ฉด ๋ค์ ํ๊ฐ๋ฅผ ์ํด while๋ฌธ์ ๋๋ฉด์ lt ํฌ์ธํฐ์ ํด๋นํ๋ ๊ฐ์ sum์์ ๋นผ์ฃผ๊ณ ํ์นธ ์ด๋์์ผ์ผ ํ๋ค.
- ์ด์ ์ sum๊ณผ m์ ๊ณ์ํด์ ๋น๊ตํ์ฌ ๊ฐ๋ค๋ฉด answer๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค.
function solution(m, arr) {
let answer = 0, sum = 0, lt = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
while (sum >= m) {
if (sum === m) answer++;
sum -= arr[lt++];
}
}
return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
๐จ๐ผ๐ซ ๊ฐ์ฌ๋ ํ์ด ๋ฐฉ๋ฒ
๋์ ํ์ด์ ๋ง์ ๋ถ๋ถ์ด ๋น์ทํ ๊ฒ์ ํ์ธํ ์ ์๋ค. ๋จ์ง sum๊ณผ m์ ์ธ์ ๋น๊ตํ๋๋์ ๋ํ ์ฐจ์ด๋ค.
function solution(m, arr) {
let answer = 0, lt = 0, sum = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum >= m) {
sum -= arr[lt++];
if (sum === m) answer++;
}
}
return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
'Algorithm > ์ธํ๋ฐ(inflearn)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JavaScript/section 5] 05 - ์ต๋ ๋งค์ถ (0) | 2022.09.20 |
---|---|
[JavaScript/section 5] 04 - ์ฐ์ ๋ถ๋ถ์์ด 2 (0) | 2022.09.19 |
[JavaScript/section 5] 02 - ๊ณตํต์์ ๊ตฌํ๊ธฐ (0) | 2022.09.18 |
[JavaScript/section 5] 01 - ๋ ๋ฐฐ์ด ํฉ์น๊ธฐ (0) | 2022.09.17 |
[JavaScript/section 4] 05 - K๋ฒ์งธ ํฐ ์ (0) | 2022.09.16 |