Pairs

문제: Pairs

난이도: Medium

 

문제 설명

 어떤 정수 배열과 값 k가 주어졌을 때, 배열의 두 요소의 차가 k인 경우가 몇 개인지 구하여라. 예를 들어 배열이 {1, 2, 3, 4}이고, k=1일 때, 요소의 차가 1인 경우는 4-3=1, 3-2=1, 2-1=1 총 3가지이므로 답이 3이다.

 

문제 해결

소스 코드

static int pairs(int k, int[] arr) {
        int result = 0;
        int len = arr.length;

        Arrays.sort(arr);

        for(int i = len-1; i > 0; i--) {
            if(arr[i]<k) {
                break;
            }
            for(int j = i-1; j >= 0; j--) {
                if(arr[i] - arr[j] == k) {
                    result++;
                }else if(arr[i] - arr[j] > k) {
                    break;
                }
            }
        }

        return result;
    }

 

해설

 먼저 배열을 오름차순으로 정렬하고, 배열의 마지막 요소(가장 큰 수)부터 차가 k가 되는 경우를 탐색하였다. 이렇게 간단한 방법으로 풀이가 가능하지만 이걸로 끝내면 시간 초과로 인해 실패한다. 따라서 반드시 두 요소의 차가 k가 나올 수 없는 영역(두 요소의 차가 k보다 큰 경우, 큰 요소의 값이 k보다 작은 경우)에 도달하면 탐색을 하지 않도록 하여 시간 낭비를 없애야 한다.