[C++] 백준 2230번 수 고르기

투 포인터 문제.

투 포인터 문제를 오랜만에 풀었는데 틀렸다.

틀린 이유 위주로 정리하겠다.

 

 

문제 풀이

수열의 길이는 최대 100,000이다.

만일 한 index마다 끝까지 탐사하게 될 경우 시간 복잡도가 100,000 x 100,000이 되므로

10,000,000,000번의 연산을 하게된다. 이는 시간 초과가 발생할 것이다.

 

따라서 다른 방법을 생각했는데, 투 포인터 방법이 생각났다.

투 포인터는 한 줄의 배열이 있을 때 두 개의 포인터를 두어서, 포인터를 front, tail (혹은 lo, hi)로 두어서 포인터만 이동시키면서 푸는 방식이다.

이 문제는 최소의 차이를 구해야 하므로 정렬 시킨 후 투 포인터로 탐색해서 풀면 된다.

주의할 점은 고르는 두 수가 같은 수일수도 있다. A[i]를 두 번 고르는 경우도 있다는 말.

정렬 시킨 후 다음과 같은 조건들로 구성시키면 된다.

나같은 경우는 시작 포인터를 0, 끝 포인터를 1로

• 반복문을 front <= tail, 그리고 tail < 수의 개수(Index가 배열의 범위를 벗어나지 않게 하기 위함)일 동안 돌려준다.
• 시작 포인터가 가리키는 수와 끝 포인터가 가리키는 수의 차이가 입력받은 최소 차이와 같다면 반복문을 종료시키고 해당 차이를 출력한다.
• 만일, 두 수의 차이가 최소 차이보다 작다면 tail 포인터의 index를 하나 증가시킨다.
• 만일, 두 수의 차이가 최소 차이보다 크다면 해당 차이와 이전에 저장해놨던 차이 중 더 작은 값을 저장시켜 놓는다.

 

위와 같은 방식으로 풀면 된다.

/*
* 백준 2230번 수 고르기
* https://www.acmicpc.net/problem/2230
* 투 포인터
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int numCnt, minDiff;
vector<int> numVec;
int ans = 2100000000; // 틀린이유 3 : 최대 차이가 20억임.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> numCnt >> minDiff;

	int input;
	for (int i = 1; i <= numCnt; i++) {
		cin >> input;
		numVec.push_back(input);
	}

	sort(numVec.begin(), numVec.end());

	int front = 0;
	int tail = 1;

	while (front <= tail && tail < numCnt) { // 틀린이유 1 : front < tail로 하면 틀림 ex.) 2 0 1 2
		int frontNum = numVec[front];
		int tailNum = numVec[tail];
		int diff = tailNum - frontNum;

		if (diff == minDiff) {
			ans = diff;
			break;
		}
		else if (diff < minDiff) {
			tail++;
		}
		else if (diff > minDiff) {
			ans = min(ans, diff); // 틀린 이유 2 : ans를 항상 더 작은 값으로 갱신해 줘야한다.
			front++;
		}
	}

	cout << ans;

	return 0;
}

코드는 크게 어려운 것이 없다. 틀린 이유를 주석으로 정리해 놨는데 하나씩 살펴보자.

1. 반복문의 범위가 front < tail이 아니라 front <= tail이다. 내가 front를 0, tail을 1로 시작을 했다. 만일 수가 두 개 있고, 최소차이가 0이라고 생각해보자. 예를 들어서 [2 0 1 2]가 입력된 것이다. front < tail의 경우 1과 2를 비교해서 차이가 1이기 때문에 1을 저장해 놓고, front에 1을 증가시킨다. 이 때, front == tail이 되므로 반복문에서 빠져나오게 된다. 따라서 front == tail로 만들거나, 시작 front, tail을 0으로 시작하고 do While문을 써도 될것 같다.(do While 방식은 확인해보지는 않았다.)
2. diff > minDiff인 조건을 찾았다고 해서 ans가 다 diff가 되는 것은 아니다. 이전에 저장해뒀던 차이의 값이 더 작을 수 도 있기 때문에 min() 메서드를 사용해서 더 작은 값으로만 갱신되도록 해준다.
3. ans의 초기화를 0으로 하면 ans 값이 갱신이 안된다. 따라서 ans값을 충분히 큰 값(최대 차이가 20억이므로 20억보다 크게)초기화 해 줘야 한다.

골드 구현 문제만 풀다가 오랜만에 알고리즘 문제를 풀어봤다.

구현 문제보다 훨씬 시간이 덜 걸리는 것 같다.

투 포인터 개념도 다시한번 정리하는 것 같아서 좋다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.