[JAVA] 26. 연속 부분 수열 ✔
2021. 10. 22. 22:01
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가지입니다.
입력
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
예시 입력 1
8
6
1 2 1 3 1 1 1 2
예시 출력 1
3
내 풀이
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i =0; i<n; i++){
arr[i] = in.nextInt();
}
int pi=0, pj =0, answer =0;
int sum = 0;
while(pj <n){
sum += arr[pj];
if(sum == m){
answer ++;
sum -= arr[pi];
pi++;
pj++;
}else if(sum <m){
pj++;
}else{
while(sum >= m){
sum -= arr[pi];
pi++;
if(sum == m){
answer ++;
}
}
pj++;
}
}
System.out.println(answer);
}
}
다른 풀이
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i =0; i<n; i++){
arr[i] = in.nextInt();
}
int pi=0, answer =0;
int sum = 0;
for(int pj=0; pj <n; pj++){
sum += arr[pj];
if(sum == m)
answer ++;
while(sum >= m){
sum -= arr[pi];
pi++;
if(sum == m){
answer ++;
}
}
}
System.out.println(answer);
}
}
728x90
'알고리즘 > JAVA' 카테고리의 다른 글
[JAVA] 28. 최대 길이 연속부분수열 ✔ (0) | 2021.10.23 |
---|---|
[JAVA] 27. 연속된 자연수의 합 (0) | 2021.10.22 |
[JAVA] 25. 최대 매출(Sliding Window) (0) | 2021.10.22 |
[JAVA] 23. 공통원소 구하기 - 복습! (0) | 2021.10.22 |
[JAVA] 24. 멘토링 (0) | 2021.10.17 |