문제
- 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을 넘지 않는 자연수이다.
출력
- 첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
- 수열의 원소값은 1,000을 넘지 않는 자연수이다.
입출력 예제
아직 포인터와 윈도우에 익숙하지 않다..
풀이 방식을 정리해보자.
1. N과 M을 입력받고 arr[ ] 배열에 값을 입력받는다.
- N : 수의 개수
- M : 특정 숫자
- arr[ ] : 수열
2. 메소드 구현으로 넘어가보자.
3. result, sum, lt를 선언하고 0으로 초기화한다. rt는 for문에서 선언한다.
- result : 결과값
- sum : M과 비교하기 위한 누적 합산값
- lt : 포인터로, 왼쪽부터 시작한다.
- rt : 포인터로, 오른쪽부터 시작한다.
4. 0부터 N까지 도는 for문을 작성하고, 익숙한 i 대신에 rt로 변수명을 바꾸어서 작성한다.
5. 맨 처음에는 arr[rt] 값을 sum에 누적한다.
- sum에는 arr[lt] 부터 arr[rt]까지의 합이 들어간다.
6. sum과 M이 동일한지 비교하고, 동일하면 결과값에 1을 더한다.
7. sum이 M보다 크거나 작을때까지 도는 while 문을 작성한다.
- M 크기를 가진 윈도우라고 생각하자.
8. sum에서 arr[lt] 값을 뺀 후에 lt를 더해준다.
- 맨 처음과 마지막 인덱스를 통해 sum 값을 변경하는 것이다.
- 아래 이미지를 참고하자. 크기가 3인 윈도우를 가지고 있다.
- 맨 처음에는 lt와 rt가 0인 상태에서 시작한다. 그 후에 for문을 통해 rt 값이 증가하면서 윈도우의 크기가 점차 늘어난다.
- 문제 예시를 참고해서 M이 6이라고 했을 때, lt = 0 이고 rt = 3 에 도달하면 sum은 1+2+1+3 = 7로, M인 6보다 크다.
- 이 때에 sum에서 lt가 0일때 값을 빼고, lt 를 1 증가시키면 결과적으로 lt = 1이고 rt = 3 인 아래 윈도우 범위가 된다.
- 2+1+3 = 6 이므로 결과값에 1이 더해진다.
- 해당 루틴을 반복하며 결과값을 출력한다.
9. sum과 M이 동일한지 비교하고, 동일하면 결과값에 1을 더한다.
수행 결과를 확인한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
