10507. 영어 공부

링크: SW ExpertAcademy ) 10507. 영어 공부

풀이

이 문제를 보고 백준에 비슷한 문제가 있었던거 같은데 결국 찾지 못했다.
처음 생각한것은 브루트포스 였지만 범위를 보니 시간초과가 나올거 같았다.

다른 분께서 투포인터로 해야한다는 얘기를 듣고 아하이럼
투포인터로 혼자 구현을 했지만 예제는 통과했지만 시간초과를 통과하지 못했다.

결국 다른분 풀이를 보고 풀었다.

먼저 이문제는 투포인트로 풀어야한다.

예제)
5 2
3 5 6 10 11

c라는 배열에 수림이가 공부한 날을 체크해야한다.

요런식으로 start와 end가 움직여야한다.
움직임의 규칙을 찾자면
변수 num은 start와 end의 거리이다.

c[end]에 방문한 적이 없고, 아직 이동횟수가 남았다면
이동횟수를 한번 줄이고, end는 앞으로 간다.
만약에 가던 도중에 방문한 적 있는 end이면 이동횟수를 줄이지 않고 전진한다.

이것은 c[end]에 방문한 적이 없고, 아직 이동횟수가 없을때까지 반복한다.
c[end]에 방문한 적이 없고, 아직 이동횟수가 없다면
start가 앞으로가야한다.
수림이가 start날에 공부한적이 없다면 이동횟수를 하나 추가, 거리는 하나 줄고 전진한다.
start날에 공부한적이 있다면 거리는 하나 줄고 전진한다.
이것을 계속 반복하고하다가.
end가 수림이가 실제로 공부한 마지막 날에 도착한다면 while문을 종료한다.

import java.util.*;
class Solution
{  
	static final int MAX = 1000001;
	static boolean[] c;
	static int N, P, max;

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			P = sc.nextInt();
			c = new boolean[1000001];
			int last=0;
			for (int i = 0; i < N; i++) {
				int tempNum = sc.nextInt();
				last = Math.max(last, tempNum);
				c[tempNum] = true;
			}
			max = P+1;
			search(last);
			System.out.println("#" + test_case + " " + max);
		}
	}

	public static void search(int last) {
		int start = 1;
		int end = 1;
		int num = 0;
		while(end<last+1) {
			if(c[end]) {
				num++;
				end++;
				max=Math.max(max, num);
			}
			else {
				if(P==0) {
					max=Math.max(max, num);
					if(!c[start]) P++;
					start++;
					num--;
				}
				else {
					P--;
					num++;
					end++;
				}
			}
		}
	}
}