좋다 [C++]

문제 링크: https://www.acmicpc.net/problem/1253

난이도: 🟡🟡🟡🟡 / GOLD4

1. 문제 설명

2. 문제 접근

• 💡 하나씩 비교해보며 찾는다면 좋은 수 하나를 찾는데 드는 시간 복잡도는 O(n²)이 되기 때문에 시간초과가 난다.
• 💡 투 포인터를 이용하면 좋은 수 하나를 찾는데 드는 시간 복잡도는 O(n log n)으로 줄일 수 있다.

1. N개의 수 중에서 어떤 수가 다른 수 두개의 합으로 나타낼 수 있는 수를 찾는 것이기 때문에 '투 포인터'를 이용하여 수를 찾는다.
2. 어떤 수와 다른 수들은 서로 달라야한다.
   • 예외처리에 유의하고 풀이한다.
     
     

3. 제출 코드

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

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

	int N;
	cin >> N;
	vector<long> nums;

	for (int i = 0; i < N; i++)
	{
		long num;
		cin >> num;
		nums.push_back(num);
	}
    
    // 투 포인터를 이용하기 위해 배열(벡터)을 정렬한다.
	sort(nums.begin(), nums.end());

	int cnt = 0;
    // 투 포인터(배열의 두 지점의 합이 target과 비교하며 배열을 순회한다.)
	for (int i = 0; i < N; i++)
	{
		long target = nums[i];
		int start = 0;
		int end = N - 1;

		while (start < end)
		{
			// 어떤 수를 찾았다면 start와 end가 서로 다른 수인지 확인한다.
			if (nums[start] + nums[end] == target)
			{
				if (start != i && end != i)
				{
					cnt++;
					break;
				}
				// 검색에서 자신을 포함하면 안된다.
				else if (start == i)
					start++;
				else if (end == i)
					end--;
			}
			else if (nums[start] + nums[end] < target)
				start++;
			else if (nums[start] + nums[end] > target)
				end--;
		}
	}
	cout << cnt;

	return 0;
}

4. 풀이 과정

문제를 읽고 주어진 수 중에서 다른 두 수의 합과 같으 수를 찾는다는 부분에서 투 포인터를 사용하면 되겠다고 생각했다.

// 처음 제출시 작성한 투 포인터 탐색
while (start < end)
{
	if (nums[start] + nums[end] == target)
	{
		cnt++;
		break;
	}
	else if (nums[start] + nums[end] < target)
		start++;
	else if (nums[start] + nums[end] > target)
		end--;
}

이렇게 짜고 나니 예제 케이스는 통과했지만 결과는 틀렸다.

문제를 다시 확인하고 내가 탐색하는 수는 다른 두 수에 포함하면 안된다는 점과 그 경우에 대한 예외처리를 추가해서 문제를 통과할 수 있었다.

// 수정한 투포인터 탐색
while (start < end)
{
	if (nums[start] + nums[end] == target)
	{
    	// nums[start]와 nums[end]가 서로 다른 수인지 확인한다.
		if (start != i && end != i)
		{
			cnt++;
			break;
		}
		// 검색에서 자신이 포함되면 다음 수로 넘어간다.
		else if (start == i)
			start++;
		else if (end == i)
			end--;
	}
	else if (nums[start] + nums[end] < target)
		start++;
	else if (nums[start] + nums[end] > target)
		end--;
}

5. 결과