[BOJ] 2230. 수 고르기 (이분탐색버전)

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

2230번: 수 고르기

투 포인터 <=> 이분탐색의 발상을 배웠습니다.

*홍보*

문제풀이 강의를 한번도 들어본적이 없다가 BarkingDog님 알고리즘 강의를 처음으로 들었는데..

이정도 강의 퀄리티면 문제풀이 강의 듣는 사람들의 입장이 이해가 가는 것 같습니다.

​

뭐랄까.. 모든 문제를 시간들여 다 풀면서 느끼면 더 좋겠지만, 현실적인 제약이 따르잖아요?

또한 수학 풀때도 느꼈지만, 아무리 아인슈타인이라도, 갑자기 제가 만든 언어로 만든 문제를 내면 맞출 수 있을까요?

그럴 수 없습니다. 기본적인 배경지식이 있어야 합니다. 이게 자료구조, 알고리즘 이라고 생각하는데 그 부분을 효율적으로 채워주는것 같습니다.

​

자료구조적인 측면은 학과 수업에서 충분히 다루어 지고, 알고리즘에서 PS에 필요한 idea들을 주는 것 같습니다. (양심상 홍보 한번 했습니다)

​

--문풀

투 포인터 챕터에서 들었는데, 이진탐색으로 풀 수 있다고 해서 풀었습니다. 대부분의 풀이를 보니 투포인터라서 올립니다.

​

idea는 N개의 숫자로 k를 찾을 때, N-1개의 숫자로 k-a 를 탐색하면 시간복잡도가 N짜리가 lgN으로 바뀌는 아이디어 입니다.

문제를 풀면 이해가 갈텐데.. 어쩔수 없군요.

​

아무튼!

​

l A[i] - A[j] l <= m 을 만족하는 가장 최소의 차이를 구하는 문제입니다.

이 문제를 A[i] <= m + A[j] 로 바꿔봅시다.

​

원래라면, 2중 for문에서 위의 식을 만족하는걸 찾으면 됩니다. O(N^2)이죠? N은 10^6 이므로 10^12라서 시간초과입니다.

O(NlgN)으로 바꾸면 2 * 10^7 정도라서.. 약 2천만 굉장히 짧게 통과 가능합니다. 물론 NlgN이 한번 더 있습니다. (정렬)

​

A[i] <= m + A[j] 인 A[i]를 어떻게 찾을것이냐?

lower_bound를 이용하면 A[i]보다 같거나 큰 가장 작은 iter를 반환합니다. ( 이분 탐색으로 구할 수 있습니다)

#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
int A[MAX];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> A[i];
	sort(A,A+n);
	int min = 2e9 + 1;
	int idx;
	for(int i = 0; i < n; i++)
	{
		idx = lower_bound(A,A+n,m + A[i]) - A;
		if(idx != n)
		{
			//값이 존재하면
			if(min > A[idx] - A[i]){
				min = A[idx] - A[i];
			}
		}
	}

	cout << min;

	
	return 0;	
}

위와 같이, 만약 lower_bound가 존재한다면 그 차이를 저장합니다.

1,3,5일때 lower_bound는 2를 리턴합니다.

ex ) 5 >= 3 + 1 이므로, 5 -1 = 4 를 저장해야합니다. 따라서 A[2] - A[0]을 저장합니다.

​

5 2

-11 -8 -5 -3 -1

일때 답이 2가 아닌 3이 나오게 됩니다.

왜냐하면,

- 8 >= 2 + - 11 이므로, -8 + 11 = 3 이 나오게 됩니다.

하지만 답은 -3 + 5 = 2 가 되어야 합니다.

따라서 모든 수를 다 봐야합니다.

​

충분히 빠른 시간이 나옵니다.

​

​

감사합니다