[HackerRank] Pairs

Problem

---

Given an array of integers and a target value, determine the number of pairs of array elements that have a difference equal to the target value.

 

Example
k = 1

arr = [1, 2, 3, 4]

There are three values that differ by k = 1: 2 - 1 = 1, 3 - 2 = 1, and 4 - 3 = 1. Return 3.

 

Function Description

Complete the pairs function below.

pairs has the following parameter(s):

• int k: an integer, the target difference
• int arr[n]: an array of integers

Returns

• int: the number of pairs that satisfy the criterion

Input Format

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

Constraints

• 2 ≤ n ≤ 10^5
• 0 ≤ k ≤ 10^9
• 0 ≤ arr[i] ≤ 2^31 -1
• each integer arr[i] will be unique

Sample Input

STDIN       Function
-----       --------
5 2         arr[] size n = 5, k =2
1 5 3 4 2   arr = [1, 5, 3, 4, 2]

Sample Output

3

Explanation

There are 3 pairs of integers in the set with a difference of 2: [5,3], [4,2] and [3,1]. .

 

---

정수 배열과 목표 값 k가 주어질 때, 배열 요소 중에서 차이가 k인 쌍의 개수를 구하는 문제입니다.

 

예제

• k = 1
• arr = [1, 2, 3, 4]

여기서 k = 1의 차이를 가지는 값이 세 쌍 있습니다: 2 - 1 = 1, 3 - 2 = 1, 4 - 3 = 1. 따라서 결과는 3이 됩니다.

 

함수 설명

함수 이름: pairs

• 매개변수
  • int k: 목표 차이 값
  • List<Integer> arr: 정수 배열
• 반환값
  • 주어진 차이 값을 만족하는 쌍의 개수 (int)

입력 형식

첫 번째 줄에는 두 개의 정수 n(배열의 크기)과 k(목표 차이 값)가 주어집니다.
두 번째 줄에는 배열의 요소가 공백으로 구분되어 주어집니다.

 

제약 조건

• 2 ≤ n ≤ 10^5
• 0 ≤ k ≤ 10^9
• 0 ≤ arr[i] ≤ 2^31 - 1
• 각 정수 arr[i]는 유일합니다.

설명 k = 2의 차이를 가지는 세 쌍이 있습니다: [5,3], [4,2], [3,1].

 

 

728x90

 

 

Solution

---

* 내가 처음 작성한 코드 - 시간 초과 문제 발생

public static int pairs(int k, List<Integer> arr) {
    // Write your code here
    int cnt = 0;
    
    for (int i = 0; i < arr.size(); i++) {  
        for (int j = i+1; j < arr.size(); j++) {
            if (arr.get(i) - arr.get(j) == k || arr.get(j) - arr.get(i) == k) {
                cnt++;
            }   
        }  
    }
    return cnt;
}

 

위 코드로 작성했더니
Time limit exceeded Allowed time limit:4 secs Your code did not execute in time. Please optimize your code. For more details on runtime environment, click the “Info” button

 

이런 메시지가 떴다. 

그래서 ChatGPT에 물어봤더니 이런 답변이 왔다. 

시간 초과 문제(Time limit exceeded)를 발생시키고 있습니다. 
이는 코드가 O(n^2)의 시간 복잡도를 가지기 때문에 발생합니다. 
이중 for 루프를 사용해 모든 가능한 쌍을 비교하면서 차이를 확인하는 방식이기 때문입니다. 
제약 조건에서 배열의 크기 n이 최대 10^5까지 갈 수 있는데, O(n^2) 복잡도는 이 범위에서 너무 오래 걸립니다.

 

그래서 코드를 이렇게 수정했다. 

 

해결 방법: Set을 이용한 최적화

이 문제는 Set 자료 구조를 활용하면 효율적으로 해결할 수 있습니다. 각 요소 x에 대해 x + k 또는 x - k가 배열에 존재하는지 빠르게 확인하는 방식으로, 시간 복잡도를 O(n)으로 줄일 수 있습니다.

public static int pairs(int k, List<Integer> arr) {
    Set<Integer> set = new HashSet<>(arr);
    int count = 0;

    for (int x : arr) {
        // 차이가 k인 쌍을 찾기 위해 x + k 또는 x - k가 있는지 확인
        if (set.contains(x + k)) {
            count++;
        }
        if (set.contains(x - k)) {
            count++;
        }
    }

    // 각 쌍이 두 번 계산되므로 총 카운트를 절반으로 나눔
    return count / 2;
}

 

 

1. Set<Integer> set = new HashSet<>(arr);
   • 배열을 Set에 넣어서 각 요소의 존재 여부를 빠르게 확인할 수 있습니다.
2. for (int x : arr)
   • 배열의 각 요소 x에 대해 반복합니다.
3. if (set.contains(x + k))
   • x + k가 set에 있는지 확인합니다. 있다면 x와 x + k가 차이가 k인 쌍을 이룹니다.
4. if (set.contains(x - k))
   • x - k가 set에 있는지 확인합니다. 있다면 x와 x - k가 차이가 k인 쌍을 이룹니다.
5. return count / 2;
   • 각 쌍이 두 번 계산되므로, 최종적으로 결과를 2로 나누어 반환합니다.

결과적으로 이 방법은 이중 루프 대신 Set을 사용해 빠르게 쌍을 찾으므로 Time limit exceeded 문제를 해결할 수 있습니다.