백준 2467 C++

• 투 포인터(Two Pointers) 알고리즘

  • 리스트 또는 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘
  • 주로 정렬된 배열 또는 리스트에서 특정 합, 차, 또는 조건을 만족하는 부분 리스트를 찾을 때 사용
  • 일반적으로 O(N)의 시간 복잡도를 가짐

• 작성 방법

  1. 포인터 초기화
  • 리스트나 배열의 시작 부분에서 두 포인터를 초기화
  • 하나는 리스트의 맨 왼쪽에서 시작하고, 다른 하나는 맨 오른쪽에서 시작
    
    
  2. 포인터 이동 반복문 수행
  • 두 포인터가 원하는 조건을 만족할 때까지 반복문을 수행
  • 현재 상태에서 원하는 조건을 만족하도록 포인터를 이동
    
    
  3. 조건 확인
  • 원하는 조건 만족 시 결과 반환 또는 기록

#include <iostream>
#include <vector> 
#include <utility>  // pair 타입 사용
using namespace std;

int main()
{
    // 입출력 속도 향상
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 입력: 배열 크기
    int n;
    cin >> n;

    // 입력: 정수 배열
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i]; 
    }

    // 투 포인터 알고리즘을 사용하여 합이 0에 가장 가까운 두 수 찾기
    int left = 0;            // 배열의 왼쪽 끝 인덱스
    int right = n - 1;        // 배열의 오른쪽 끝 인덱스
    int sum = 2e9;            // 현재까지의 최소 합 (큰 값으로 초기화)
    pair<int, int> p;          // 결과를 저장할 변수

    // 두 포인터가 엇갈릴 때까지 반복
    while(left < right)
    {
        int a = v[left];
        int b = v[right];
        
        // 현재 두 수의 합의 절댓값이 현재 최소 합보다 작으면 갱신
        if(abs(a + b) < sum)
        { 
            sum = abs(a + b); 
            p = { a, b }; 
        }

        // 두 수의 합이 0보다 작으면 left를 증가시켜 더 큰 수를 선택
        if(a + b < 0)
        { 
            left++;  
        }
        // 두 수의 합이 0보다 크거나 같으면 right를 감소시켜 더 작은 수를 선택
        else
        {
            right--; 
        }
    }

    // 결과 출력
    cout << p.first << " " << p.second << endl;

    return 0;
}