#1449 수리공 항승

# 문제

# 입력 및 출력

# 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> pipe;

int main() {
	int n, l, p, cnt = 0;
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> p;
		pipe.push_back(p);
	}
	sort(pipe.begin(), pipe.end());
	for (int i = 0; i < n; i++) {
		int k = i;
		for (int j = i + 1; j < n; j++) { // 첫번째 구간에서 하나의 테이프로 막을 수 있는 구간을 찾음
			if (pipe.at(i) + l <= pipe.at(j)) continue;
			else k = j;
		}
		cnt++; 
		i = k; // 두번째 테이프가 붙어야 하는 부분
	}
	cout << cnt << "\n";
}

처음에 작성한 코드는 위와 같음

이중 for문을 사용해서 첫번째 누수 구간에서 테이프를 붙였을 때 막을 수 있는 모든 누수 구간을 찾음

그 다음 누수 구간부터는 두번째 테이프를 사용해서 막아야 하기 때문에 i를 다시 설정해줌

 

근데 이렇게 되면 시간 복잡도가 n^2으로 좋지 못하다

그래서 반복문을 줄일 수 있는 방법이 있는지 찾아보았다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> pipe;

int main() {
	int n, l, p, cnt = 1;
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> p;
		pipe.push_back(p);
	}
	sort(pipe.begin(), pipe.end());
	int tape = pipe.at(0) + l;
	for (int i = 0; i < n; i++) {
		if (pipe.at(i) < tape) continue;
		else {
			tape = pipe.at(i) + l;
			cnt++;
		}
	}
	cout << cnt << "\n";
}

반복문 자체는 줄었다

tape 변수를 사용해서 첫번째 누수 구간에서 테이프를 붙였을 때 누수를 막을 수 있는 구간을 저장해둔다

그래서 이 위치보다 누수 위치가 커지면 다음 테이프를 사용해야 하고 다시 tape 변수를 갱신해준다

 

 

메모리와 시간은 동일하다

복잡하지 않은 코드라서 그런 것 같다