BOJ) 수들의 합 2 (2003 번)

수들의 합 2

2003번: 수들의 합 2

N개의 수열에서 i ~ j 번 째의 값들의 합이 M이 되는 경우를 구하는 문제다.

N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) 의 조건이 주어진다.

투포인터는 슬라이딩 윈도우와 유사하지만 다른 점은 바로 탐색 구간의 길이가 정해져있지 않다는 것이다.

투포인터를 활용해서 푸는 문제인데, 익숙하지 않아서 기록에 남겨둔다.

 

우선, 시작점 탐색을 도와줄 left와 끝점 탐색을 도와줄 right를 선언해주었다.

그리고 문제의 조건인 합을 구하기 위한 변수 sum, 정답을 출력해줄 answer를 선언해주었다.

 

while문을 반복적으로 돌면서, 포인터에 따른 현재까지의 합이 m 이상이 되면 left를 한 칸 늘려주면서 합을 줄여주었다. 같은 방식으로, m보다 작은 값이라면 right 포인터를 한 칸 늘려주어 합을 증가시켰다.여기서, right가 out of index가 나지 않도록 break를 해주는 것이 중요하다.위의 세 조건 이후에도 loop가 진행된다면, 현재까지 더한 값이 주어진 숫자 m과 같은지 확인하고 count해주는 방식으로 문제를 풀었다.

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SumOfNumbers_2003 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());

    int[] numArr = new int[n];
    for(int i=0; i<n; i++) {
      numArr[i] = Integer.parseInt(st.nextToken());
    }
    br.close();
    solution(n,m,numArr);
  }

  private static void solution(int n, int m, int[] numArr) {
    int left =0, right =0, sum =0, answer=0;

    while(true) {
      if(sum >= m) { // 현재까지의 합이 m 이상이면 left를 옮겨준다.
        sum -= numArr[left++];
      } else if(right ==n) {
        break;
      } else { // 아니라면 right를 옮겨준다.
        sum += numArr[right++];
      }
      if(sum == m) { // m인 경우를 카운트
        answer++;
      }
    }

    System.out.println(answer);
  }
}