[java] 1940 주몽

1. 문제 링크 및 문제

https://www.acmicpc.net/problem/1940

2. 해결 방법 생각해보자 ...

N개의 재료 중 두 개의 재료로 M이 되는 갑옷을 만들어야 함.
N의 최댓값이 15000일 때 값을 하나씩 비교한다면 15000*15000으로 2초 안에 해결할 수 없음
-> 투포인터를 사용하여 두 개씩 값을 비교함

• start = 0 , end = N-1 로 비교하려면 정렬된 상태의 배열에 투포인터를 적용해야 함
  • arr[start]+arr[end] 값이
    • 크면 end --
    • 작으면 start ++
    • 같으면 count++, end --, start++

시간복잡도

정렬 = Arrays.sort(arr) => O(nlogn)
투포인터 => O(2n)
이므로 정렬 후 투포인터를 사용해서 M의 값이 되는 경우의 수를 찾는 방법은 O(nlogn)이 소요됨

3. 코드

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

public class Main {

	static int N,M;
	static int[] arr ;

	public static int stoi(String str){
		return Integer.parseInt(str);
	}

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

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

		N = stoi(br.readLine());
		M = stoi(br.readLine());
		arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) arr[i] = stoi(st.nextToken());

		// 반복문을 통한 누적합 확인은 시간초과가 나므로 
			// 투포인터

		Arrays.sort(arr);
		System.out.println(twoPointer());

	} 

	public static int twoPointer(){
		int start = 0 ; // 시작 인덱스값
		int end = N-1 ; // 끝 인덱스값
		int count = 0 ; // 합이 M이 되는 개수

		while(start < end){
			int sum = arr[start] + arr[end];
			if(sum == M){
				count ++ ;
				end --;
				start ++;
			}else if(sum > M) end -- ;
			else start ++ ;
			
		}

		return count ;
	}

}