SWEA - 영어 공부(C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS

SW Expert Academy

 

문제 이해 자체는 어렵지 않다. 만약 답을 구할 수 있도록 러프하게 구해보면

 

1 3 4 5

 

라고 들어온다고 가정할 때 1에서 시작해서 N 모두 보기 , 2에서 시작해서 모두보기 해서 총 N * N의 시간이 걸리도록 하는 것은 쉽다.

그러나 20만 * 20만 = 4천억으로 어림도없다.

 

그래서 처음 생각해낸 것은 1 3 4 5에서 1에서 최고수를 구하고 3에서 최고수를 구하는 것을 이분탐색으로 찾아내는 식으로 문제를 풀었다. 예제는 맞았지만 시간초과가 발생했다.

N log N 으로도 풀어낼 수 없었다. 

 

그래서 구글링을 해보니 이 문제는 이분탐색의 투포인터문제였다.

투포인터는 개념자체는 알고있긴한데 언제 사용해야할지 정확히 모르겠다.

 

#include <iostream>
#include <vector>
using namespace std;

bool isStudy[1000001];
int n, p;

void init(){
	for(int i = 0; i < 1000001; i++) isStudy[i] = false;
}

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

	int T; cin >> T;

	for (int t = 1; t <= T; t++) {
        init();
		cin >> n >> p;
		
		int isMax = 0;

		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			isMax = max(isMax, tmp);
			isStudy[tmp] = true;
		}

		int hi = 1;
		int lo = 1;

		int point = p;

		int answer = p + 1;
		while (hi < isMax + 1) {
			if (isStudy[hi]) {
				hi++;			
                answer = max(answer, hi - lo);
			}
			else if (point > 0) {
				point--;
				hi++;
			}
			else if (point == 0) {
                 answer = max(answer, hi - lo);
				if (isStudy[lo] == false) point++;
				lo++;
			}
		}
		cout << '#' << t << ' ' << answer << '\n';

	}
}