시간복잡도 줄이기 2) 하나 고정하기

1. 하나 고정하고 나머지 값을 통해 찾기

---

• 배열에서 세가지 값의 합을 구하는 등의 작업을 할 때, 하나의 값을 고정시켜두고 나머지 값들만 투포인터를 통해서 계산하기

 

2. 문제

---

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

• 이 문제는"중간에서 만나기"를 쓰면 추가 공간이 필요하여 메모리가 터진다.
• n = 5000이기 때문에 n^2은 25,000,000이 되고, 여기서 long long값과 인덱스 2개를 int로 저장하면
  • 25,000,000 * (8 + 4 + 4)  = 400,000,000 
  • 400MB 메모리 필요하므로 메모리 초과가 될 것이다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n;
vector<long long> vec;
long long minValue = LLONG_MAX;
vector<long long> answer;

void Print()
{
	sort(answer.begin(), answer.end());

	for (const auto& a : answer)
	{
		cout << a << " ";
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int num;
		cin >> num;
		vec.push_back(num);
	}

	sort(vec.begin(), vec.end());

	for (int i = 0; i < n - 2; ++i)
	{
		int l = i + 1;
		int r = n - 1;

		while (l < r)
		{
			long long temp = vec[i] + vec[l] + vec[r];

			if (abs(temp) < minValue)
			{
				minValue = abs(temp);

				answer.clear();
				answer.push_back(vec[i]);
				answer.push_back(vec[l]);
				answer.push_back(vec[r]);
			}

			if (temp < 0)
				l++;
			else if (temp > 0)
				r--;
			else
			{
				Print();
				return 0;
			}
		}
	}
	Print();
}