[백준 2470][💛5] 두 용액 (투포인터 알고리즘)

🚀 난이도

💛 골드 5

🚀 문제

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

예제 입력 1 
5
-2 4 -99 -1 98
예제 출력 1 
-99 98

🚀 내 풀이 ⭕

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2000000000
using namespace std;

vector<int> answer(2);
int main() {
    int N;
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    sort(arr.begin(), arr.end()); // 정렬 필수!

    int start = 0; // start 은 왼쪽 끝에서
    int end = N - 1; // end 은 오른쪽 끝에서 시작
    int min = INF; // 현재까지 0 에 가장 가까웠던 합
    while (start < end) {
        int sum = arr[start] + arr[end];

        if (min > abs(sum)) {
            min = abs(sum);
            answer[0] = arr[start];
            answer[1] = arr[end]; 

            if (sum == 0)
                break;
        }

        if (sum < 0) 
            start++;
        else 
            end--;
    }

    cout << answer[0] << " " << answer[1];
}

양쪽 끝에서 출발한 두 포인터가 서로 반대 방향으로 다가와서 좁혀지는 형태의 투포인터 알고리즘이다. start -> <- end 요렇게!

• start -> 방향
• end <- 방향

서로의 합이 가장 0 에 가까운 두 수를 구해야하기 때문에 먼저 오름차순 정렬을 한 후, 양쪽 끝에서부터 두 포인터를 이용하여 0 에 가까운 두 수를 구해나간다.

min은 현재까지 구한 두 수의 합 중 가장 0 에 가까웠던 합. (가장 “가까웠던” 이니까 절대값으로 넣어야 한다.)

• 1️⃣ 먼저 오름차순 정렬을 한다. (음수거나 작을 수록 왼쪽, 양수거나 클 수록 오른쪽에 위치하도록)
• 2️⃣ 양쪽 끝의 두 포인터가 가리키는 원소끼리 더하여 최대한 두 수의 합이 0 에 가깝도록 두 포인터를 업데이트 해나간다.
  • arr[start] + arr[end] < 0
    • 0 보다 작으므로 두 수의 합이 더 커져야 0 에 가까워질 것이다. 그러므로 더 커져야하기 떄문에 start를 증가시킨다. (작은 값을 더 큰 값으로 대체)
  • arr[start] + arr[end] > 0
    • 0 보다 크므로 두 수의 합이 더 작아야 0 에 가까워질 것이다. 그러므로 더 작아져야하기 떄문에 end를 감소시킨다. (큰 값을 더 작은 값으로 대체)
• 3️⃣ min 업데이트 하기
  • arr[start] + arr[end] < min
    • 기존에 구했던 두 수의 합보다 더 작은 합이 나왔으니 정답 후보가 될 수 있다. min과 answer를 업뎃한다.
    • 혹시 이미 0 이 나왔으면 더 찾을 필요 없으므로 종료.

4 -99 -1 7 -2

• 우선 정렬하기 👉 -99 -2 -1 4 7
• -99 -2 -1 4 7 : -99 + 7 < 0 이므로 더 커져야 함 (92)
• -99 -2 -1 4 7 : -2 + 7 > 0 이므로 더 작아져야 함 (5)
• -99 -2 -1 4 7 : -2 + 4 > 0 이므로 더 작아져야 함 (2)
• -99 -2 -1 4 7 : -2 + -1 < 0 이므로 더 커져야 함 (3)
  • start >= end 이므로 종료

답은 가장 0 에 가까웠던 (2) -2 4 가 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기