BOJ_2467

😄 밑에 초등부 문제라고 써있다. 어나더 레벨의 친구들이 풀었나보다.

2467번 : 용액

• N개의 용액 중에 2개를 뽑아 0과 가장 가까운 수를 만들면 되는 문제이다.
• 하나씩 모두 비교하는 2중 For문을 사용하면 N^2의 시간복잡도가 생겨난다.(10만 * 10만)
• 그래서 나는 For문을 단 한번 N의 시간복잡도로 풀 수 있는 두 포인터를 생각했다.
• 인덱스를 가장 앞과 가장 뒤에 하나씩 배치하고 인덱스에 따른 수 두개를 더했을 때
  • 잠깐!! 두 포인터를 쓰려면 오름차순 정렬부터 해준다.
  • 양수가 나오면? 양수의 힘이 세니깐 오른쪽의 인덱스를 낮춰준다.
  • 음수가 나오면? 음수의 힘이 세니깐 왼쪽 인덱스를 높여준다.
  • 0이 나오면? 무조건 나간다. 0이 되면 그게 답!!

💻 두 포인터

int start = 0, end = N - 1, result = 2000000000;
    int resultx, resulty;
    while (start < end)
    {
        int sum = v[start] + v[end];
        if (abs(sum) < abs(result))
        {
            result = sum;
            resultx = v[start];
            resulty = v[end];
        }
        if(sum > 0)
            end -= 1;
        else if(sum < 0)
            start += 1;
        else if(sum == 0)
            break;
    }
 

• if(abs(num) < abs(result)) 구문은 답을 찾기 위한 if문이다.

💻 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    vector<int> v;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    int start = 0, end = N - 1, result = 2000000000;
    int resultx, resulty;
    while (start < end)
    {
        int sum = v[start] + v[end];
        if (abs(sum) < abs(result))
        {
            result = sum;
            resultx = v[start];
            resulty = v[end];
        }
        if(sum > 0)
            end -= 1;
        else if(sum < 0)
            start += 1;
        else if(sum == 0)
            break;
    }
    cout << resultx << " " << resulty << endl;
}

😳 두 포인터에 대해서 알고 있다면 쉽게 풀수 있는 문제지만 그렇지 않다면 조금은 어려울 수도 있을 문제다.