[G5] 백준 2230번 수 고르기 C++ 투 포인터, 정렬

리뷰

 

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

투 포인터를 사용하여 O(N)의 시간 복잡도로 풀 수 있는 문제

 

 

전역 변수

• n : 수열의 길이를 저장할 변수
• m : 두 수의 최소 차이를 저장할 변수
• ans : 정답을 저장하기 위한 변수
• lst : 수열의 정보를 저장하기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, n개의 원소를 lst배열에 입력 받아준다.
2. lst배열을 오름차순으로 정렬해 준다.
3. 두개의 포인터 l, r을 각각 0으로 초기화 해준다.
4. l이 n - 1보다 작다면 반복하여 루프를 실행해 준다.
5. 정수형 변수 diff에 lst의 r번 인덱스값에서 l번 인덱스 값을 뺀 값을 저장해 준다.
6. 만약 diff가 m이상이라면 ans와 diff를 비교하여 더 작은 값을 ans에 저장해 준 뒤 l을 증가시켜 준다.
7. 아니라면 r을 증가시켜 준다.
8. 탐색이 종료된 후에 ans에 저장된 값을 출력해 준다.

 

참고 사항

음수가 섞일 수 있기 때문에 오른쪽 포인터를 n - 1로 했을 경우 그리디하게 풀 수 없는듯 하다.

 

 

정답 코드

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

int n, m, ans = 2e9;
int lst[100000];

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	sort(lst, lst + n);

	int l = 0, r = 0;
	while (l < n - 1) {
		int diff = lst[r] - lst[l];
		if (diff >= m) {
			ans = min(ans, diff);
			l++;
		}
		else r++;
	}
	cout << ans;
}