[백준/BOJ] 백준 13561번 : House Rental

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

13561번: House Rental

map을 이용한 투 포인터를 이용하여 문제를 해결했다. 이때 두 포인터의 합이 음수이고, 그때 합의 절댓값이 홀수 일 때 와 같은 경우는 합을 2로 나눈 위치에서 -1 한 위치를 가운데로 하는 것과 같은 것을 고려해야 한다.

 

코드

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

int k, n;
vector<pair<int, int>> point_type;
map<int, int> check; //(종류,개수)
map<int, int>::iterator it;
int max_len = 2000000001;
int result = 1000000001;

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

	cin >> k >> n;

	for (int i = 0; i < n; i++)
	{
		int point, type;
		cin >> point >> type;

		point_type.push_back(make_pair(point, type));
	}

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

	int left = 0;
	int right = 0;
	int mid;
	int len;
	while (1)
	{
		if (right == point_type.size())
		{
			if (check.size() == k)
			{
				//양쪽 끝의 합이 음수일때
				if (point_type[left].first + point_type[right - 1].first < 0)
				{
					//양쪽 끝 합의 절대값이 홀수 일때
					if (abs(point_type[left].first + point_type[right - 1].first) % 2 == 1)
					{
						mid = ((point_type[left].first + point_type[right - 1].first) / 2) - 1;
						len = (point_type[right - 1].first - mid);

						if (len <= max_len)
						{
							if (len == max_len)
								result = min(result, mid);
							else
								result = mid;

							max_len = len;
						}

					}

					else
					{
						mid = ((point_type[left].first + point_type[right - 1].first) / 2);
						len = (point_type[right - 1].first - mid);

						if (len <= max_len)
						{
							if (len == max_len)
								result = min(result, mid);
							else
								result = mid;

							max_len = len;
						}

					}

				}

				else
				{
					mid = ((point_type[left].first + point_type[right - 1].first) / 2);

					len = (point_type[right - 1].first - mid);

					if (len <= max_len)
					{
						if (len == max_len)
							result = min(result, mid);
						else
							result = mid;

						max_len = len;
					}

				}

				check[point_type[left].second]--;

				if (check[point_type[left].second] == 0)
					check.erase(point_type[left].second);

				left++;
			}

			else
			{
				break;
			}
		}

		else
		{
			if (check.size() == k)
			{
				//양쪽 끝의 합이 음수일때
				if (point_type[left].first + point_type[right - 1].first < 0)
				{
					//양쪽 끝 합의 절대값이 홀수 일때
					if (abs(point_type[left].first + point_type[right - 1].first) % 2 == 1)
					{
						mid = ((point_type[left].first + point_type[right - 1].first) / 2) - 1;
						len = (point_type[right - 1].first - mid);

						if (len <= max_len)
						{
							if (len == max_len)
								result = min(result, mid);
							else
								result = mid;

							max_len = len;
						}
					}

					else
					{
						mid = ((point_type[left].first + point_type[right - 1].first) / 2);
						len = (point_type[right - 1].first - mid);

						if (len <= max_len)
						{
							if (len == max_len)
								result = min(result, mid);
							else
								result = mid;

							max_len = len;
						}
					}

				}

				else
				{
					mid = ((point_type[left].first + point_type[right - 1].first) / 2);
					len = (point_type[right - 1].first - mid);

					if (len <= max_len)
					{
						if (len == max_len)
							result = min(result, mid);
						else
							result = mid;

						max_len = len;
					}
				}

				check[point_type[left].second]--;

				if (check[point_type[left].second] == 0)
					check.erase(point_type[left].second);

				left++;
			}

			else
			{
				if (check.count(point_type[right].second) == 0)
				{
					check.insert(make_pair(point_type[right].second, 1));
				}

				else
				{
					check[point_type[right].second]++;
				}

				right++;
			}
		}


	}

	cout << result << "\n";

	return 0;
}