[알고리즘] C++ 백준 2230 수 고르기

백준 2230

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

2230번: 수 고르기

풀이 전 나의 생각

N개의 정수로 이루어진 수열 A에 대하여 두 수를 골랐을 때

그 차이가 M이상이면서 제일 작은 경우를 구해야 한다.

 

조건

- 1 ≤ N ≤ 100,000

- 0 ≤ M ≤ 2,000,000,000

- 0 ≤ |A[i]| ≤ 1,000,000,000

 

과정

N, M, A[i] 모두 int형의 범위를 넘지 않기 때문에 데이터 타입을 int로 설정해준다.

 

N이 10만이기 때문에 for문만을 이용한 풀이를 진행한다면 시간초과가 일어날 것이다.

따라서 탐색 횟수를 O(N)으로 줄여줄 수 있는 투 포인터를 사용하여 풀어야한다.

 

배열의 시작점에 시작과 끝을 가리키는 포인터 2개가 있다고 가정하고

arr[end] - arr[start] 값을 구하며 M을 기준으로 포인터를 조정한다.

 

1. 시작점을 기준으로 M 이상이 되는 arr[end] - arr[start] 값을 구해준다.

for (int start = 0; start < N; start++)
	{
		while (end < N && arr[end] - arr[start] < M) end++;
		if (end == N) break;
		ans = min(ans, arr[end] - arr[start]);
	}

 

start가 0 일때 M 이상이 될 수 있는 값을 구해내야 한다.

 

while문을 보면 end는 N의 범위를 넘어선 안되며, arr[end] - arr[start] 즉, 현재 포인터가 가리키는

끝과 시작값을 뺀 값이 M 보다 더 작을 때 end 포인터를 증가시켜주며 최적의 포인터를 구해낸다.

 

if(end == N)으로 범위를 넘어서면 루프를 벗어나게 해주고

아니라면 현재 M 이상이면서 최소인 값을 구했기 때문에 최종값을 갱신해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int arr[100001];

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

	int N, M;
	int ans = INT_MAX;
	cin >> N >> M;


	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + N);

	int end = 0;

	for (int start = 0; start < N; start++)
	{
		while (end < N && arr[end] - arr[start] < M) end++;
		if (end == N) break;
		ans = min(ans, arr[end] - arr[start]);
	}

	cout << ans;
}