자바로 백준1940 풀기

• 실버 4단계 문제

풀이)

주어진 재료 N개는 15000개 이하이고, 이를 통해 만들 숫자 M은 1천만 이하이다.
숫자 두 개의 합이 M이 되는 가짓수를 구해야 하는데,단순히 for문을 쓰면 최악의 경우 10억번의 연산을 해야 한다.
따라서 주어진 배열을 정렬한 후(시간복잡도 O(nlogn)) 오름차순 정렬된 배열을 투포인터로 해결할 것이다.

내 코드)

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int m = Integer.parseInt(reader.readLine());

        int[] material = new int[n];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for (int i=0; i<n; i++) {
            material[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        for(int start=0; start<n; start++)  {
            int sum = 0;
            int end = start+1;

            while (end<n) {
                sum = material[start];
                sum += material[end++];
                if (sum == m) {
                    cnt++;
                    break;
                }
            }

        }

        System.out.println(cnt);

    }
}