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

1. 문제

 

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

2230번: 수 고르기

 

2. 풀이

 

처음 풀이는 단순하게 for문 2개를 활용하는 방법이였지만, 역시나 시간복잡도가 너무 커서 틀렸었다. (당시 시간복잡도는 O(N^2))

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		diff = A[i] - A[j];
		if (diff > m && diff < minDif)
			diff = minDif;
	}
}

 

사실 투 포인터 강의를 이분탐색 강의보다 먼저 들었었는데, 이분탐색 강의를 듣고 난 후 더 효율적인 풀이를 찾을 수 있었다. 꽤 간단하기도 했고!

키 포인트는 바로 '정렬'이라고 생각한다. 처음에 이중 for문으로 접근했을 당시에는 무작위로 정렬된 배열을 가지고 도대체 어떤 식으로 차이를 구해야 할까, 시간복잡도 O(N^2)를 줄일 수 있는 방법이 있을까 고민했었다. 근데, sort 함수를 써주게 되면 배열을 다루는 데 훨씬 편하다.

두 번째 포인트는 바로 '규칙'을 찾는 것이다. sort된 배열을 기준으로 생각을 해본다면, 이 문제는 아래와 같은 규칙을 가진다.

 

1)  st가 증가함에 따라 A[en] - A[st]가 m 이상이 되는 최초 지점 en의 값은 커짐.

2) st에 대해 A[en] - A[st]가 m 이상이 되는 최초의 지점 en을 찾은 이후에는 굳이 en을 증가해 그 이후 값들에 대한 차이를 알아낼 필요가 없음! (∵ 우리는 배열을 이미 정렬해놓은 상황이고 우린 m 이상의 최소 차이값을 알면 됨. en을 증가시켜 A[en] - A[st]을 아무리 구해본다고 해도 최소 차이값보다 커질 것임.)

 

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

int n;
int m;
int diff;
int minDiff = 2000000000; //애초에 minDiff는 최고로 큰 값으로 설정해버리기

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

	cin >> n;
	cin >> m;
	int A[n] = { 0 };
	int en = 0;

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

	sort(A, A + n);

	for(int st = 0; st < n; st++) {
		while (en < n && A[en] - A[st] < m) {
			en++;
		}
		if (en == n) break;
		minDiff = min(minDiff, A[en] - A[st]) //최소값 비교할 때는 min 함수 활용
	}

	cout << minDiff;
}

 

3. 이슈 및 배운 점

 

• 배열을 다룰 때는 sort 함수를 쓰는 것도 고려하자. 훨씬 문제를 간단하게 접근할 수 있다!
• 최소값을 구할 때는 min 함수를 활용해보자. 한 줄에 최소값을 구해버릴 수 있다.
• 컴파일 에러 조심..! 오타로 인해 컴파일 에러가 몇 번 떴었다😥
• 알고리즘 공부 존버하자🥺 뚝딱뚝딱 풀어낼 때까지 화이팅!