1940. 주몽

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

1940번: 주몽

이 문제는 투 포인터와 정렬을 개념을 활용하여 푸는 문제입니다. N의 최대 범위가 15000까지이기 때문에 시간 복잡도에 있어서 다소 자유도가 있는 편입니다. 정렬을 사용해도 크게 문제가 없습니다. 입력받은 N개의 재룟값을 정렬한 후에 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근해주시면 됩니다.

 

*풀이

1. 재료 데이터를 배열에 저장한 후 오름차순 정렬합니다. 여기서 Arrays.sort를 써도 시간 복잡도상 크게 문제가 되지는 않습니다.

 

 

 

2. 투 포인터 i와 j를 양쪽 긑에 위치시킨 후 문제의 조건에 적합한 포인터 이동 원칙을 활용하여 탐색을 수행합니다. 일단 투 포인터 이동 원칙을 간단하게 정리해보자면 이렇습니다.

 

** 투 포인터 이동 원칙 **

* arr[i] + arr[j] > M: j--;

=> 번호의 합이 M보다 크므로 큰 번호 index를 감소시켜줍니다.

 

* arr[i] + arr[j] < M; i+=;

=> 번호의 합이 M보다 작으므로 작은 번호 index를 증가시켜줍니다.

 

* arr[i] + arr[j] == M; i++; j--; count++;

=> 양쪽 포인터를 모두 이동시키고 count를 증가시켜줍니다.

 

3. 2단계를 i와 j가 만날 때까지 반복합니다. 반복이 끝나면 count를 출력해줍니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
 
        int arr[] = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
 
        int i = 0;
        int j = arr.length - 1;
        int count = 0;
 
        while (i < j) {
            if (arr[i] + arr[j] < M) {
                i++;
            } else if (arr[i] + arr[j] > M) {
                j--;
            } else {
                i++;
                j--;
                count++;
            }
        }
        System.out.println(count);
    }
}