[백준 - 3274] 실버4 두 수의합 (투포인터)

www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

1. 유형

두 포인터

 

2. 풀이법

단순히 이중for문을 사용하면 시간 초과가 난다

그렇기 때문에 정렬후, 이분탐색을 사용해야한다

 

3. 코드

import java.util.Arrays;
import java.util.Scanner;

public class back_3273두수의합 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int inp[] = new int[N];
		for (int i = 0; i < N; i++) {
			inp[i] = sc.nextInt();
		}
		int x = sc.nextInt();
		Arrays.sort(inp);
		int answer=0;
		for (int i = N-1; i >=0 ; i--) {
			int mid = i/2;
			if(inp[i]+inp[mid] > x) {
				while(mid!=-1) {
					if(inp[i]+inp[mid]==x) {
						answer++;
						break;
					}
					mid--;
				}
			}
			else if(inp[i]+inp[mid] < x) {
				while(mid!=i) {
					if(inp[i]+inp[mid]==x) {
						answer++;
						break;
					}
					mid++;
				}
			}else if(inp[i]+inp[mid]==x) {
				answer++;
			}
		}
		System.out.println(answer);
	}
}
//

중앙값을 찾은 후, 타깃보다 크면 mid를 하나씩 줄이면서 합을 비교.

if(inp[i]+inp[mid] > x)

중앙값을 찾은 후, 타깃보다 크면 mid를 하나씩 늘이면서 합을 비교.

else if(inp[i]+inp[mid] < x)