백준 2230번: 수 고르기

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

2230번: 수 고르기

 

 

0. 알고리즘 분류

 정렬, 두 포인터

 

 

1. 문제

 N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

 

 

2. 풀이

 우선, 계산하기 쉽게 정렬 알고리즘으로 주어진 수열을 오름차순으로 정렬시켜준다. 그리고 두 포인터(start, end)를 이용해 반복문을 돌린다. 두 포인터의 차잇값이 M과 같으면, break로 탈출해서 출력하면 끝이다. 그렇지 않다면, 수열의 끝까지 포인터를 움직이며 탐색하면 된다.

 

 상당히 시간이 빡빡한 문제같다. start++의 위치에 따라 시간초과 떴다.

 

 

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;
int a[100001];

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++) {
		scanf("%d", a+i);
	}
	sort(a, a+n);
	
	int start = 0;
	int end = 1;
	int ans = 2e9+1;
	while (end < n) {
		int temp = a[end] - a[start];
		if (m == temp) {
			ans = temp;
			break;
		}
		else if (m > temp) {
			end++;
			continue;
		}
		
		if (temp < ans) {
			ans = temp;
		}
		start++;
	}
	
	printf("%d", ans);	
	return 0;
}