[백준] 2230번: 수 고르기 C++로 풀어보기

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

2230번: 수 고르기

2230번 설명

생각

투 포인터를 사용하여 문제를 해결 할 수 있다.

 

(투 포인터에 대해서 궁금하다면 밑의 링크를 클릭해서 바킹독님의 강의를 보면 된다. 이 문제에 대한 풀이도 해주신다!)

https://www.youtube.com/watch?v=I_0aAKzu0m8&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=21

 

포인터 두 개 st, en을 둔다.

 

1. en을 옮긴다.
2. en - st >= m 이상일 때를 찾는다.
3. en-st가 min보다 작다면min을 갱신한다.
4. st를 옮긴다.
5. 2번 조건에 만족하면 min을 갱신한다.(불만족할때까지)
6. 불만족하면 en을 옮긴다.

 

위 과정을 반복하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int arr[100005];
int least = 0x7fffffff; // 차이의 최솟값을 저장할 변수

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

	
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) { // 입력
		cin >> arr[i];
	}

	sort(arr, arr+n); // 오름차순 정렬

	int en = 0; // en을 0으로 둔다
	
	for (int st = 0; st < n; st++) { 

		while (en < n && arr[en] - arr[st] < m) { // en이 n보다 작고 두 수의 차이가 m보다 작으면
			en++; // 포인터 en을 증가시킨다
		}
	
		if (en == n) { // en이 n이라면 (범위를 넘어갔으므로)
			break; // while문을 종료한다
		}

		int bet = arr[en] - arr[st];


		if (bet < least) { // bet이 least보다 작다면
			least = bet; // least에 bet을 저장한다
		}
		
	}

	cout << least; // least를 출력한다

}

 

결과

2230번 결과

 

큰 수를 나타낼 때는 0x7fffffff를 나타내면 좋다는 사실을 배웠다(0x7fffffff는 표현할 수 있는 가장 큰 32비트 값이다.).