Menu

Subscribe

[JAVA/SWEA] 10507: 영어 공부

HEESOO on Swea

👀 문제

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

👊 도전

1. 설계

  1. 해킹할 수 있는 p개를 적절히 사용하여 영어 공부를 매일한 max값을 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution
{
    
	static boolean[] visit;
	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();
			int[] input=new int[N];
			for(int i=0;i<N;i++) input[i]=sc.nextInt();
			visit=new boolean[1000001];
			max=P+1;
			for(int day:input) visit[day]=true;
			
			search();
			System.out.println("#"+test_case+" "+max);
		}
	}
	public static void search() {
		int start=1;
		int end=1; 
		int cnt=0; 
		while(end<visit.length) {
			if(visit[end]) { 
				cnt++;
				end++;
				max=Math.max(max, cnt);
			}
			else { 
				if(P==0) {
					max=Math.max(max, cnt);
					if(!visit[start]) P++; 
					start++; 
					cnt--; 
				}
				else {
					P--;
					cnt++;
					end++;
				}
			}
		}
	}
}

3. 결과

실행결과 🤟 성공 🤟
처음에는 DFS로 구현했는데 30일을 넘어가니까 시간이 오래 걸리고 무한루프에 빠져서 다른 방법을 생각했다.

4. 설명

  1. 공부하지 않은 날은 해킹하면서 최대 공부한 날을 리턴한다
    • end는 지금까지 체크한 일 수를 뜻한다.
    • cnt는 지금까지 공부했다고 기록된 날을 뜻한다.
    • visit[]를 이용해 공부한 날은 visit[idx]=true로 한다.
    • 체크하는 end일(visit[end])이 진짜로 공부한 날이라면 cnt++한다. 그 다음 날을 체크하기 위해 end++한다. cnt가 갱신되었으므로 max를 체크한다.
    • !visit[end]는 실제 공부하지 않았다는 뜻이다.
    • P를 이용하여 해킹 가능한지 여부를 체크한다. P!=0이면 아직 해킹이 가능한 것이므로 end날을 해킹한다. 해킹을 한 번 썼으므로 P–, 해킹해서 end날이 공부한 날이라고 기록되었으므로 cnt++, 다음 날 체크를 위해 end++이다.
    • P==0은 해킹 횟수를 모두 썼다는 뜻이다. 이때는 앞에서부터 해킹한 날을 찾아 취소하고, 현재 end날에 해킹한다.
    • 해킹한 날을 취소할 것이므로 cnt값이 변경되어야 한다. 따라서 지금까지의 cnt를 max와 체크해 저장한 후 cnt–한다. visit[start]로 start날이 해킹한 날이라면 그 날을 해킹 취소한다. 따라서 해킹할 기회가 생긴 것이므로 P++. start날 해킹 체크가 완료됐으므로 start++로 다음 탐색에 사용한다. 여기서 end++를 하지 않았기 때문에 while문으로 다시 들어가면 P!=0이므로 해킹 체크를 할 수 있다.

👏 해결 완료!