문제

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

---

설명

주어진 문제의 최대 값을 보면 15000이다. 이는 이중 for문을 사용할 경우
2억2천이 나오므로 2초가 초과되어 시간 초과가 나와 다른 방법을 이용하여 풀어야 된다.

주인장은 정렬과 두개의 포인터를 이용하는 투 포인터를 이용하여 O(nlogn) 시간으로 해결하려고 한다.

투 포인터

투 포인터는 계산하려는 배열의 범위나 해당 배열 값들을 이용하는 알고리즘이라고 생각하면 된다.

투 포인터 원칙

투 포인터를 사용할때는 위와 같은 규칙이 있다
(문제에 따라서는 위 규칙이 바뀌는 경우도 있으므로 유도리 있게 사용할 것)

또한 while(endPoint>startPoint) 이 부분에서 조건도 달라 지는 경우가 있으므로 상황에 맞게 작성 하면 된다.

정렬

투 포인터를 활용하기로 결정했다면 투 포인터에 따라오는 문제들을 알고 있어야 된다.

투 포인터는 정렬을 먼저 하고 난 후 이용하면 원하는 값을 빠르게 구할 수 있다

또한 java에서는 배열의 정렬 기능을 함수로 제공해주고 있다.

int[] A = new int[10]
//{1, 6, 5, 4, 2, 3}

Arrays.sort(A);

위 코드를 이용하여 아래와 같이 정렬이 된다.

투 포인터 이용

재료 값이 5일 때

마지막에서는 while문 조건 때문에 반복문을 빠져 나가게 된다.

이후 cnt를 출력해주면 문제에 대한 답을 도출해 낼 수 있다.

---

코드

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

public class J1940 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(bufferedReader.readLine());
        int maxValue = Integer.parseInt(bufferedReader.readLine());
        int[] numArray = new int[num];
        int startPoint = 0;
        int endPoint = num-1;
        int cnt = 0;
        numArray[0] = 0;
        String[] input = bufferedReader.readLine().split(" ");
        for(int i = 0; i<num; i++){
            numArray[i] = Integer.parseInt(input[i]);

        }
        Arrays.sort(numArray);

        while((endPoint > startPoint)){
            if(numArray[startPoint]+numArray[endPoint] <maxValue)
                startPoint++;
            else if (numArray[startPoint] + numArray[endPoint] > maxValue) {
                endPoint--;
            }
            else if (numArray[startPoint] + numArray[endPoint] == maxValue) {
                cnt++;
                startPoint++;
                endPoint--;
            }
        }
        System.out.println(cnt);
    }
}