[백준] 3273 두 수의 합 - HashSet(해시셋) + 정렬(Sort) + 투포인터(Two Pointer) JAVA

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

코드설명

해시셋 + 정렬 + 투포인터를 활용합니다.

 

첫번쨰 방법은, X - arr[i] = arr[j] 인 배열값이 수열에 존재한다면 arr[i] + arr[j] = X 를 만족한다는 의미입니다.

그러므로 HashSet을 활용하여 삭제시키며 처리합니다.

 

두번쨰 방법은, 정렬한뒤 가장 작은값과 가장 큰값을 더해서, 원하는 X값보다 같다면 일치하니 값을 1개 증가시킵니다.

원하는 X값보다 작다면, 정렬된 수열에서 작은값의 인덱스를 1개 증가시킵니다.

원하는 X값보다 크다면, 정렬된 수열에서 큰 값의 인데스를 1개 감소시키며 찾아갑니다.

코드

해시셋을 사용해서 진행한 코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static int N, M, C, X;
    public static int answer = 0;
    public static HashSet<Integer> hashset = new HashSet<>();
    public static int[] arr;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			hashset.add(arr[i]);
		}
		st = new StringTokenizer(br.readLine());
		X = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			int otherV = X - arr[i];
			hashset.remove(arr[i]);
			if(hashset.contains(otherV) == true) {
				answer += 1;
				hashset.remove(otherV);
			}
		}		
		System.out.println(answer);
	}
}

정렬과 투포인터를 활용한 코드

package Main;

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

public class Main {
    public static int N, M, C, X;
    public static int answer = 0;
    public static int[] arr;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		X = Integer.parseInt(st.nextToken());
		
		Arrays.sort(arr);
		int lo = 0, hi = N - 1;
		while(lo + 1 <= hi) {
			
			int left = arr[lo];
			int right = arr[hi];
			
			int sum = left + right;
			if(sum == X) {
				answer += 1;
				lo += 1;
				hi -= 1;
			}else if(sum > X) {
				hi -= 1;
			}else if(sum < X) {
				lo += 1;
			}
		}
		
		System.out.println(answer);
	}
}