백준 문제풀이 : (1253) 좋다 - C/C++

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

1253번: 좋다

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	256 MB	Gold 4	정렬, 이분탐색, 두 포인터

 

 

문제 

 

 

풀이

시간 제한이 2초이고, 주어지는 수의 개수가 최대 2000개다. 단순히 반복문만을 이용해 문제를 풀이할 경우 시간복잡도가 n의 3승 이상으로 늘어나기 때문에, 시간을 단축할 수 있는 방법을 찾아봐야 한다.

 

나는 모든 수의 조합을 검토할 수 있지만, 시간 복잡도를 n의 2승 내에 풀 수 있는 '두 포인터' 방법을 사용해보기로 했다. 

 

두 포인터 알고리즘을 사용하기 위해서는 주어지는 배열이 정렬 상태여야 한다. 

 

정렬된 배열의 양 끝에 두 포인터를 각각 배치한다. 이 상태에서 두 포인터(첫번째 수, 두번째 수)가 가리키는 수의 합이 K가 되는 수가 몇 개 인지 셀 수 있는 방법은 아래와 같다.

 

만약, 첫번째 수 + 두번째 수 의 합이 K보다 작다 → 첫번째 수의 포인터를 +1 한다.

만약, 첫번째 수 + 두번째 수 의 합이 K보다 크다 → 두번째 수의 포인터를 -1 한다.

(만약, 첫번째 수 포인터 혹은 두번째 수 포인터가 합이되는 수를 가리키는 포인터와 같아지면 건너뛴다.)

만약, 첫번째 수 + 두번째 수 의 합이 K와 같다. → 찾는 조건에 부합하므로 count를 1 증가하고, 반복문을 종료한다.

 

즉, 위의 과정을 주어진 모든 수(최대 N개의 수)에 적용하면 된다.

 

 

코드 작성

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    int nums[n];
    int count=0, one=0, two=n-1;
    
    for (int i=0 ; i<n ; i++) {
        scanf("%d", &nums[i]);
    }
    
    for (int i=0 ; i<n ; i++) { //배열을 정렬해준다.
        for (int j=i+1 ; j<n ; j++) {
            if (nums[i]>nums[j]) {
                int temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
            }
        }
    }
    
    for (int i=0 ; i<n ; i++) {
        one=0;
        two=n-1;
        while (one<two) {
            if(one==i) { one++; continue; } 
            if(two==i) { two--; continue; } 
            //a+b=c의 a,b,c는 모두 다른 수여야 함. 
            //one 혹은 two 포인터가 i와 같은 수를 가리키면 건너뛴다.
            
            if (nums[one]+nums[two] < nums[i]) one++;
            else if (nums[one]+nums[two] > nums[i]) two--;
            else { count++; break; }
        }
    }
	printf("%d", count);
}

 

 

END.