[Java] 투포인터 | 백준 1253 좋다

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

 

접근 방법

투포인터를 사용하여 두 수의 합을 구하고 그 합이 타겟과 일치하는지를 확인

이를 위해 배열의 정렬이 선행되어야 함

Arrays.sort(arr);

int count = 0;
for(int i=0; i<arr.length; i++){
    if(isGoodNumber(arr[i], i))
        count++;
}

 

배열 정렬 이후 해당 타겟 넘버가 배열 내의 두수의 합으로 만들 수 있는 수(좋은 수)인지 확인하는 isGoodNumber(int target, int target_idx) 메서드를 호출하고 좋은 수일 경우(true) count++하여 좋은 수의 개수를 구한다.

 

isGoodNumber 메서드 구현

단순히 배열 내의 두 수가 배열 내의 타겟 값과 일치하는 지만 확인한다면, 두수의 합이 타겟 값과 같은 경우 return true, 타겟 값 보다 클 경우 right 포인터 1 감소,타겟 값보다 작을 경우 left 포인터 1증가시키며 확인하면 된다.

그러나 left나 right 포인터가 가리키는 수에 타겟값이 있다면 타겟 값이 다른 두 수의 합으로 나타내야한다는 조건을 만족시키지 못한다.

즉, 타겟 값은 포인터가 가리키면 안된다. 이를 방지하지 위해, left포인터와 right 포인터가 타겟 값과 같을 경우를 체크한다. 

만약 left 포인터가 타켓을 가리키고 있을 경우 left++ 후 continue, right 포인터가 타겟을 가리킬 경우 right--후 continue 처리한다.

이를 통해 타겟을 제외한 두수의 합이 타겟 값과 같음을 보장할 수 있다.

private static boolean isGoodNumber(int target, int target_idx){
    int left = 0; int right = N-1;

    while(left < right){
        if(left == target_idx){
            left++;
            continue;
        }
        
        if(right == target_idx){
            right--;
            continue;
        }

        int currentSum = arr[left] + arr[right];

        if(currentSum == target) 
            return true;
        
        if(currentSum > target){
            right--; continue;
        }
        left++;
    }
    
    return false;
}

 

 

이 문제가 낮은 정답률과 생각보다 높은 난이도로 평가되는 이유가 있을텐데 아직 왜인지 잘 모르겠다. 뭔가 쉽게 풀려 좀 찝찝해 다른 사람들의 질문들을 찾아보고 내가 고민하지 않았던 부분을 알아봐야겠다.