[SWEA] 10507번 영어 공부- 투 포인터(java)

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

SW Expert Academy

문제 자체는 간단하고 이해하기 쉽다.

연속해서 출석을 할수록 높은 점수를 받는다.

이미 출석이 되어있고, P 개를 수정하여 가장 큰 연속된 수를 찾는 것이다.

 

핵심

이러한 문제가 대부분 그러하듯이 브루트포스로 풀게 되면 시간초과가 나오게 된다.

이 문제는 투 포인터를 사용해야 한다.

 

예제)
5 2
3 5 6 10 11

 

visited라는 배열에 공부한 날을 체크한다.

이미 출석한 날을 체크

 

이후 연속해서 출석할 수 있는 그래프를 그렸다.

변수 num의 경우 start와 end의 거리이다.

visited [end]에 방문한 적이 없고, 아직 이동 횟수가 남았다면 이동 횟수를 줄이고 end를 증가시킨다.

가던 도중 방문한 적이 있는 end라면 이동 횟수를 줄이지 않고 전진한다.

visited [end]에 방문한 적이 없고, 아직 이동 횟수가 없을 때까지 반복한다.

visited [end]에 방문한 적이 없고, 이동 횟수가 없다면 start를 증가시킨다.

start날에 공부한 적이 없다면 이동 횟수를 증가시키고, 거리를 감소시킨다.

start날에 공부한 적이 있다면 거리를 하나 줄이고 전진한다.

 

이제 코드를 통해 확인해 보자.

 

 

정답 코드

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

    public static void main(String args[]) {
        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();
            visited = new boolean[MAX];
            int last=0;
            for (int i = 0; i < N; i++) {
                int study = sc.nextInt();
                last = Math.max(last, study);
                visited[study] = 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(visited[end]) {
                num++;
                end++;
                max=Math.max(max, num);
            }
            else {
                if(P==0) {
                    max=Math.max(max, num);
                    if(!visited[start]) P++;
                    start++;
                    num--;
                }
                else {
                    P--;
                    num++;
                    end++;
                }
            }
        }
    }
}

해설

방문한 일정의 최댓값은 100000이기 때문에 visited를 100001로 잡았다.

last의 경우 탐색범위를 결정하기 위해 사용된다.

max = P+1로 설정해 둔 이유는 최소한 P를 모두 이어 붙인 경우의 값이기 때문이다.

search를 통해 위에서 설명한 대로 투 포인트를 진행한다.

쉽게 설명하면 P를 이용해서 갈 수 있다면 쭉 가고 P를 다시 용한 경우 start를 증가시키고, 다시 전진하는 느낌이다.

우리가 지정한 last까지 확인을 하며 값을 찾아간다.

 

배운 점

투 포인터를 몰랐기 때문에 위와 같은 풀이를 생각하지 못했다.

이중 for문을 사용하여 풀려했지만 시간복잡도에서 걸려버렸다.

알고리즘을 공부할수록 많은 알고리즘이 존재한다는 것을 느낀다.

새롭기도 하고 재미있다고 생각된다. 더 열심히 해야겠다.