[HackerRank] Pairs (JAVA)

문제

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

 

For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: 2 - 1 = 1, 3 - 2 = 1, 4 - 3 = 1

 

 

입력

The first line contains two space-separated integers n and k, the size of arr and the target value.
The second line contains n space-separated integers of the array arr.

 

 

출력

An integer representing the number of pairs of integers whose difference is k.

 

 

제한

2 <= n <= 10⁵

 

0 < k < 10⁹

 

0 < arr[i] < 2³¹ - 1

 

each integer arr[i] will be unique.

 

 

풀이

이진 탐색, 해쉬 맵으로, 총 2가지 방식으로 풀 수 있는 문제였습니다.

 

어떤 배열이 주어지고 target value인 k가 주어지는데, 배열 내의 두 요소를 빼서 k를 만드는 경우의 수를 구해야 합니다. 위의 세 가지 방식을 모두 소개하도록 하겠습니다.

 

 

풀이 - 이진 탐색

이진 탐색을 하기 전에 우리가 문제를 보고 가장 먼저 떠오르는 방법은 브루트포스일 것입니다. 하지만, 이것은 시간복잡도가 O(N²)이기 때문에 시간초과가 날 여지가 있습니다. 따라서, 시간복잡도를 적어도 O(NlogN)으로 줄여야하는데 이진 탐색 알고리즘을 통해 이를 해결할 수 있습니다.

 

먼저, 브루트포스를 사용한다면 배열에서 요소 하나를 선택하고, 그 요소를 제외한 나머지 요소와 전부 뺄셈을 하면서 k를 만족하는 경우가 있는지 체크할 것입니다. 여기서 나머지 요소와 뺄셈을 하여 k를 만족하는 경우가 있다고 가정하면,  'arr[i] - x = k'인 x가 배열 안에 반드시 존재할 것입니다. ('x - arr[i] = k'를 사용해도 무방합니다.) 그리고 식을 이항하면 'x = arr[i] - k'가 됩니다. 그렇다면, 굳이 배열의 요소를 하나 하나 살펴볼 필요 없이 이진 탐색을 사용하여 x가 배열 안에 존재하는지 체크하면 됩니다.

 

저는 이진 탐색을 구현하지 않고, Arrays 내의 binarySearch() 메소드를 활용하였습니다. 이 메소드는 원하는 값이 배열 안에 없을 경우 -1이 아니라 배열에서 자기 차리를 찾아서 음수로 반환해 줍니다. 자세한 설명은 이곳을 참고하시길 바랍니다. 따라서, 반환되는 위치 값이 0이상 arr.length - 1이하여야 찾으려는 값의 위치가 존재하는 것입니다.

 

굳이 내장 메소드를 쓰지 않아도, 원래 기본적인 이진 탐색을 구현하여 사용하셔도 무방합니다. 다만, 배열은 오름차순으로 정렬되어야 합니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드 - 이진 탐색

 

 

풀이 - 해쉬 맵

위 풀이처럼 이진 탐색 알고리즘으로도 시간 안에 해결됩니다. 그렇다면, 시간 복잡도가 O(NlogN)이 과연 최상의 알고리즘인걸까요? 아닙니다. 해쉬 맵을 사용하면, 시간 복잡도를 O(N)으로 줄일 수 있습니다.

 

key를 배열의 요소, value는 true로 설정하여 해쉬 맵을 정의한 후, 'x = arr[i] - k'를 만족하는 x가 해쉬 맵 안에 존재하는지 확인하면 됩니다. ('x = arr[i] + k'를 사용해도 무방합니다.)

 

처음에 해쉬 맵에 배열의 값을 넣는 과정이 O(N)이고, 배열의 요소를 탐색하면서 경우의 수를 세는 과정이 O(N * 1)이므로 총 시간 복잡도는 O(N)이 됩니다. 참고로, 해쉬 맵에서 containsKey() 메소드의 시간복잡도는 O(1)입니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드 - 해쉬 맵

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.