📌강의 정리
앞의 문제보다 조금 더 어렵다.
lt, rt 두개의 포인터를 이용해서 풀어보자
lt=rt=0이기에 sum은 0이고 이제 lt는 가만히 rt는 오른쪽으로 증가해서
sum은 4가 된다.
새롭게 숫자가 추가되면 그 숫자를 포함한 연속부분수열을 구해야 한다.
3이 추가되면 3과 1,3을 구해야 한다. 그래야 중복을 회피하며 구할 수 있다.
그 다음으로 다시 1이 추가되면 1이 포함된 연속부분수열을 구해야 한다.
이런식으로 반복하면 되는데 그 수는 rt-lt+1을 하면 된다.
sum이 m보다 커지면 lt가 증가하며(- -)sum을 구해준다.
즉, rt가 증가하면서도 구하고 lt가 빠지면서도 구해야한다.
추가되면 무조건 최소 한개는 있다.
이 문제의 핵심은 부분수열을 구해야하는 구간을 정해주고
그 구간에서의 모든 부분수열을 구해주는것이다.
투포인터는 lt를 미리0으로 해두고 포문에서 rt를 움직여서 구한다.
이 문제는 answer+=rt-lt+1을 해서 개수를 계속 더해간다.
중간 while문에서 sum>m일때 sum-=arr[lt++]를 해주어서
우리가 부분수열의 개수를 구하는 구간을 조절한다.
📌느낀점
문제는 강사님이 압도적이다.
나는 하드코딩으로 심지어 범위가 늘어나면 나의 알고리즘이 통할지도 미지수이지만
강사님은 확실히 통할것이다.
알고리즘에는 아주 어려운 수학지식은 아니지만 그래도 적당한 수학지식이 응용되면
상당히 접근이 좋아지는 것 같다.
항상 번뜩이는 아이디어를 여러각도에서 잘 생각해보아야 한다.
이 문제에서는 5이하가 충족되는 수열이면 그 부분수열도 5이하가 무조건 충족되기에
그 개수를 바로더해주는 공식을썼다. 문제에서 요구하는 조건을 잘 노려보자
(220616 + )풀었다. 그것도 꽤 짧은 시간내에 이번 항해99를 진행하며 알고리즘에서 얻은
제일 큰 수확은 코드를 짜기전에 모든 흐름을 생각해보고 논리적으로 전개가 되면
그때 코딩을 하는 것이다. 이 방법으로 해야 가장 짧은 시간에 확실한 알고리즘을 짤 수 있다.
//220616
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = 0;
let sum = 0;
let lt = (rt = 0);
//rt는 0부터 arr.length까지 한번 반복한다.
for (rt = 0; rt < arr.length; rt++) {
sum = 0;
//lt는 rt의 반복문내에서 rt부터 0을 향해 반복하되
for (lt = rt; lt >= 0; lt--) {
//lt와 rt사이의 수들을 더하고
sum += arr[lt];
//그 수가 m이하이면 answer를 더하고
if (sum <= m) answer++;
//그 수가 m초과이면 반복을 종료한다.
if (sum > m) break;
}
}
return answer;
}
let a = [1, 3, 1, 2, 3];
console.log(solution(5, a));
</script>
</body>
</html>
//나의 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=0; lt=0; res=0;
let n=arr.length;
for(let rt=0;rt<n;rt++){
res += arr[rt];
if(res <= m){
answer++;
console.log(arr[rt])
if(rt === n-1 && res != arr[rt]) answer++;
}
else if(res > m){
lt++;
rt = lt-1;
res = 0;
}
}
return answer;
}
let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
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){
sum-=arr[lt++];
}
answer+=(rt-lt+1);
}
return answer;
}
let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)' 카테고리의 다른 글
| 6.학급 회장(Hash Map) (0) | 2022.06.18 |
|---|---|
| 5.최대 매출(Sliding Window) (0) | 2022.06.17 |
| 3.연속부분수열1(Two Pointers Algorithm) (0) | 2022.06.15 |
| 2.공통원소구하기(Two Pointers Algorithm) (0) | 2022.06.14 |
| 1.두 배열 합치기(Two Pointers Algorithm) (0) | 2022.06.13 |