[ 백준 / 1253 ] 좋다 (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : 이분탐색, 투포인터  
풀이 시간 : 51분 

문제 풀이 

대락난 감;;; 했던 문제. 문제의 이해를 잘못해서 삽질을 엄청 한 문제이다. 처음 문제에 접근했을 때는, 해시맵을 사용해서 배열의 데이터들을 저장한 다음, 2중 반복문을 돌면서 해시맵에 키가 존재한다면, ans에 더해주려고 하였다. 하지만, 틀렸습니다. 를 받았고 이유를 찾아보다가 여러 상황이 있음을 깨달았다.

 

1. 입력되는 값의 크기는 오름차순으로 주어지지 않는다.

2. 같은 입력값이 들어올 수 있다.

3. 한 번 선택된 GOOD수(좋다)는 다시 선택되면 안된다.

4. GOOD수를 만들 때는 선택된 나머지 두 수가 포함되면 안된다.

 

또한, $N ≤ 2000$이라서 2중 반복문으로 풀어도 시간초과가 나지 않을 것이라 생각했는데, 시간초과가 났다. 따라서 어떤 방법으로 풀어야하지 .. 고민하다가 투포인터에 이분탐색을 적용하기로 하였다.

 

사실 엄밀히 말하면 이분탐색은 아니다. 왜냐하면 이번에는 left와 right의 인덱스에만 접근하고, 중앙값을 정해두지 않기 때문이다.

이전에 이분탐색에 대해 다룰 때는 left와 right 인덱스를 정하고, 중앙값(mid)를 검색 변수로 설정하여 탐색을 진행하였다. 하지만, 이번에는 두 값의 합 정보만 있으면 되기 때문이다. 

 

따라서, 먼저 입력 배열을 오름차순으로 정렬해주었다. 이후, 반복문을 순회하며 찾고자하는 target값을 지정(`target = arr[idx]`)해 주었고, `left = 0, right = n - 1;`로 설정하여 left ≥ right가 될 때까지 투포인터를 진행하였다.

 

값이 같다고 무작정 정답 + 1을 하지 않았고, 조건 4번을 참고하여 또한번 예외처리를 진행해주었다. 그리고 오름차순으로 정렬해주었기 때문에, target 값을 mid 변수로 생각하여 새로 계산된 good수가 target보다 작으면 left++ 해주었고, 아닌 경우에는 right-- 해 주었다.

 

코드

/*
좋다 !

N개의 수 중에서 어떤 수가 다른 두 개의 합으로 나타낼 수 있는 수의 개수
수의 위치가 다르면 값이 같아도 다른 수이다. -> 
풀이:
투포인터를 하용해 매칭시키기
- 문제의 입력이 같은 값이 들어올 수도 있고, 그 중에서도 사용되어진 녀석은 또 카운트되면 안된다.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, tmp;

int main() {
	INIT;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		arr[i] = tmp;
	}

	// 순차적으로 정렬
	sort(arr.begin(), arr.end());

	int ans = 0;
	// 찾고자 하는 녀석은 자기 자신과 다른 수들의 합이여야 한다.
	for (int idx = 0; idx < n; idx++) {
		int target = arr[idx];    // 찾고자 하는 녀석
		int left = 0, right = n - 1;
		// 투포인터 시작
		while (left < right) {
			int good = arr[left] + arr[right];
			if (target == good) {
				// 예외처리 ( 현재 인덱스 녀석들(left, right)이랑 idx랑 달라야한다. )
				if (left != idx && right != idx) {
					ans++;
					break;
				}
				// 현재 idx랑 left가 만나기 전이라면 left + 1
				// 이미 만났다면, rignt - 1
				if (left == idx)
					left++;
				else
					right--;
			}
			// 같은 값을 가지지 않았다면, 이분탐색 범위 조절
			else {
				// target값보다 작다면, left를 키워주어 good 값 올리기
				if (good < target)
					left++;
				else
					right--;
			}
		}
	}
	
	cout << ans << '\n';

	return 0;
}

배운 점 

생각보다 바로바로 아이디어가 떠오르지 않아서 당황했다. 아직 투포인터, 이분탐색, 그리디, dp, 자료구조는 문제를 더 많이 풀어봐야 겠다고 생각했다 ... 살짝 우울했지만 어쩌겠습니까 ㅋ 해내야지 ^^ 

추가로 나는 visual studio나 pycharm 을 사용하여 알고리즘 풀이를 진행하고 있는데, 실제 코딩테스트에서는 이런 ide를 제공하지 않기 때문에 홈페이지 자체에서 자동완성과 디버깅 없이 풀어보는 연습을 진행해야 할 것 같다.