투포인터

배열에서 원래 이중 for문으로 O(n^2)으로 처리되는 작업을 2개의 포인터의 움직임으로 O(n)으로 해결하는 알고리즘

 

대표적인 문제 2230 수 고르기

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

 

나의 직관적인? 생각으로 짠건

int n, m;
int arr[100002];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int st = 0, en = 0;
	int ans = 0x7f7f7f7f;

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

	while (st < n) { //st가 마지막에 n까지오면 끝나는 것이고
		if (arr[en] - arr[st]>=m) { //두수의 차이가 m보다 크거나 같으면
			ans = min(ans, arr[en] - arr[st]); //ans에 최소값을 넣어주고
			st++; //st를 ++
		}
		else {//else에서는 en을++해주려고 하는데
			if (en == n - 1) st++; en이 n을 넘어가버리면 안되기문에 st를++해서 while이 종료되게 해주고
			else en++; //나머지는 en을 ++해주는걸로 처리
		}
	}
	cout << ans;
}

 

아래는 다른 분의 코드다

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x14/2230.cpp

int n, m;
int arr[100005];
int minn = 0x7fffffff;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a, a+n);
  int en = 0;
  for(int st = 0; st < n; st++){ //st를 0부터 n-1까지 돌면서
    while(en < n && a[en] - a[st] < m) en++; //en이 n보다 작거나 차이가 m보다 작으면 en++해주고
    if(en == n) break; // en이 범위를 벗어날 시 종료
    minn = min(minn, a[en] - a[st]); //st와en이 범위안에 있고 차이가 m보다 크거나 같으면 최소값 저장
  }
  cout << minn;
}

나는 while문을 계속 돌아서 st와 en을 +1씩 해주는 반면

이 코드는 한번의 st에서 en을 계속 더해준다음 최소값에 대한 처리를 한다