Two Sum

안녕하세요. 오늘은 Two Sum 코딩 테스트 문제에 대해서 분석해 보려고 합니다.

난이도 : Easy

Input: arr[] = {0, -1, 2, -3, 1}
        sum = -2
Output: -3, 1
         Valid pair exixts.
         
// If we calculate the sum of the output, 1 + (-3) = -2

Input: arr[] = {1, -2, 1, 0, 5}
       sum = 0
Output:
        No valid pair exists.

문제의 요지는 Array 내부의 수의 2개의 값을 더했을 때 Sum의 값이 있는 경우는 "Valid pair exists."를 출력하도록 하고 만약 Sum의 값이 없는 경우에는 "No valid pair exists."를 출력하도록 하는 문제입니다.

간단히 생각해 보았을 때 Array를 Loop 돌면서 Sum 해보고 있는 경우와 없는 경우를 찾으면 될 것 같아 보입니다.

그럼 간단히 코딩을 해보겠습니다.

public class TwoSum {
	static boolean checkPair(int A[], int size, int x) {
		for (int i = 0; i < (size - 1); i++) {
			for (int j = (i + 1); j < size; j++) {
				if (A[i] + A[j] == x) {
					return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int A[] = { 0, -1, 2, -3, 1 };
		int x = -2;
		int size = A.length;

		if (checkPair(A, size, x)) {
			System.out.println("Valid pair exists");
		} else {
			System.out.println("No valid pair exists.");
		}
	}
}

A [] Array의 0번부터 Loop를 돌고 다음 Loop에서는 1번 Index부터 Loop를 돌면서 계산을 해보면 SUM의 값과 같은 두 개의 수가 있는지 확인을 할 수 있을 것이라 생각하여 코드를 작성했습니다. 이렇게 작성했을 경우에 문제의 요구사항에 대해서는 만족하여 정확한 답을 찾아낼 수 있습니다.

하지만 2중 for-loop가 있기 때문에 해당 코드의 시간 복잡도가 O(n^2)으로 볼 수가 있습니다.

그럼 좀 더 이 알고리즘을 개선할 수 있는 방법을 알아보겠습니다.

public class TwoSum {
	static void checkPairs(int arr[], int sum) {
		HashSet<Integer> s = new HashSet<Integer>();
		for (int i = 0; i < arr.length; ++i) {
			int temp = sum - arr[i];
            
			if (s.contains(temp)) {
				System.out.println("Valid pair exists. ");
			} else {
				System.out.println("No valid pair exists.");
			}
			s.add(arr[i]);
		}
	}

	public static void main(String[] args) {
		int A[] = { 0, -1, 2, -3, 1 };
		int n = -2;
		checkPairs(A, n);
	}
}

위 코드는  Hash를 사용하여 처리한 코드로써 Array의 Loop를 돌면서 Sum에서 해당 값을 찾아서 빼면 그 값이 Hash에 존재하는지에 따라서 결과를 출력하는 코드입니다. 위와 같이 구현했을 때는 for-loop가 1번만 진행해도 원하는 결과를 얻을 수 있습니다. 그렇기에 해당 코드의 시간 복잡도는 O(n)으로 먼저 작성한 O(n^2)보다 속도가 개선되었다고 볼 수 있습니다.

 

해당문제의 코드는 아래의 링크에서 확인하였으며 별도로 학습한 내용을 포스팅하였습니다.

 

출처 : https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks