[BOJ] 1940: 주몽(JAVA)

백준 1940: 주몽

 

풀이

 

제공된 배열을 정렬해준 뒤,

left와 right로 포인트 이동을 해주며 구해주면 된다.

투포인터를 사용하면 O(N^2)를 O(N)만큼 효율적이다.

 

right는 배열의 맨 뒤에서 부터 시작하고,

left는 0번째 배열부터 시작해서 

 

1️⃣ arr[left]+arr[right] < M 일 경우, left++

2️⃣ arr[left]+arr[right] > M 일 경우, right--

3️⃣ arr[left]+arr[right] == M 일 경우, left++ right-- cnt++

 

전체코드

package 백준renew;

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

public class 실버4_1940_주몽 {
	static int N, M;
	static int arr[];
	static boolean visited[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		arr = new int[N];
		visited = new boolean[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		int left = 0;
		int right = N-1;
		int cnt = 0;
		while(left < right) {
			int sum = arr[left] + arr[right];
			if(sum < M) {
				left++;
			}else if(sum > M) {
				right--;
			}else {
				left++;
				right--;
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
}