[C++] 1253번: 좋다

링크

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

1253번: 좋다

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입출력 예제

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 

8

힌트

3,4,5,6,7,8,9,10은 좋다.

코드

#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


int main(void)
{
    vector<long long> nums;
    int inputNum;
    int result = 0;

    cin >> inputNum;

    for (int i = 0; i < inputNum; i++)
    {
        long long tempNum;
        cin >> tempNum;
        nums.push_back(tempNum);
    }

    // 값을 찾는 투포인터 알고리즘을 위한 정렬
    sort(nums.begin(), nums.end());

    // inputNum 횟수만큼 투포인터 알고리즘 실행
    for(int i = 0; i < inputNum; i++)
    {
        long long target = nums[i]; // 찾을 값
        int start = 0;
        int end = nums.size() - 1;

        while(start < end)
        {
            long long sum = nums[start] + nums[end];

            if( sum == target )
            {
                // 자기 자신을 연산조건으로 하면 패스
                if(start == i)    start++;
                else if(end == i)    end--;

                // 자신을 제외한 값들로 합을 찾았으면 성공
                else
                {
                    result++;
                    break;
                }
            }

            // 합이 찾는 값보다 작으면
            else if(sum < target)    start++;
            // 합이 찾는 값보다 크면
            else    end--;
        }
    }

    cout << result << endl;
    return 0;
}

풀이

투포인터 알고리즘을 사용하여 해결

투포인터 알고리즘이란?

배열의 첫번째 인덱스를 start, 마지막 인덱스를 end라고 정한다.

start와 end의 합은 sum, 찾을 목표인 수는 Target이라고 한다.

 

이 때, sum이 Target보다 작으면 Start를 오른쪽으로, 크다면 End를 왼쪽으로 옮긴다.

Sum=8, Target =9 이므로 Start를 오른쪽으로 옮긴다.

 

만약 Target을 찾지 못한다면 Start나 End는 누가 어느방향으로 가던간에 만나게 될 것이다.

이 때, 반복문을 종료하여 탐색을 종료하게 된다.

 

이러한 알고리즘을 통해 결과를 도출해보자.

 

• 투포인터 알고리즘 실행 전, 백터를 sort함수를 이용해 정렬하여 특정값을 찾을 수 있게 함
• 백터의 양 끝을 각각 start와 end  지점으로 설정하고, 두 지점의 합을 target으로 지정한 백터와 비교함
  합이 타겟보다 작으면 start를 한칸 오른쪽으로 이동, 크면 end를 한칸 왼쪽으로 이동함
  두 지점이 만나면 while문 종료
• 합과 타겟이 일치한다면 합에 사용한 백터의 인덱스들이 타겟의 인덱스와 겹치는지 확인,
  start가 타겟의 인덱스와 겹치면 start를 한칸 오른쪽으로 옮기고 end가 겹치면 한칸 왼쪽으로 옮긴다.
• 모든 조건을 통과하고 합과 타겟이 같다고 증명되었으면 result를 1 증가시키고 target을 변경