N개의 수로 이루어진 수열이 주어짐
이 수열에서 연속 부분 수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하시오
- 첫째 줄에 N ( 1<= N <= 100,000 ),M ( 1<= N <= 100,000 ) 이 주어진다.
- 수열의 원소값은 1,000을 넘지 않는 자연수임
- 첫째 줄에 경우의 수를 출력한다.
< 입력 >
8 6
1 2 1 3 1 1 1 2
< 출력 >
3
첫 줄에 N , 둘째 줄에 M을 입력한다.
import java.util.Scanner;
public class Inflearn28 {
public int Solution(int N ,int M, int[] A) {
int sum = 0; // 연속 수열의 합을 저장할 변수
int answer =0 ; // 출력을 위한 변수
int lt = 0;
for(int rt = 0; rt<N; rt++) {
sum += A[rt];
if(sum == M) {
answer ++;
}
while(sum>=M) {
sum -= A[lt++];
if(sum == M) {
answer ++;
}
}
}
return answer;
}
public static void main(String[] args) {
Inflearn28 inflearn28 = new Inflearn28();
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int[]A = new int[N];
for(int i=0; i<N; i++) {
A[i] = scanner.nextInt();
}
System.out.println(inflearn28.Solution(N,M,A));
}
}
N 개의 숫자를 배열에 넣어주고,
배열의 왼쪽부터 차례대로 탐색을 할 변수 LT ,RT 를 만들어준다 .
RT 는 증가하면서 원하는 합이 되면 answer 을 증가시켜주고 ,
sum이 M(원하는 합) 보다 크거나 같아진다면
배열에서 lT의 값을 빼주고 인덱스를 증가시켜주어 다시 sum이 M과 같은지 검사한다.
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의
자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성
www.inflearn.com
'Java' 카테고리의 다른 글
#11 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 학습 회장 ( Hash ) (0) | 2023.07.22 |
---|---|
#10 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 최대 길이 연속 부분 수열 (0) | 2023.07.22 |
#8 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 펠린드롬 (0) | 2023.02.13 |
#7 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 회문 문자열 (0) | 2023.02.10 |
#6 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 중복문자제거 (0) | 2023.02.10 |