[알고리즘] 슬라이딩 윈도우(백준 12847, 12891 -Java)

[알고리즘] 슬라이딩 윈도우(백준 12847, 12891)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

자 모든 준비와 마음이 섰으니 기초부터 차근차근 공부해보자!

 

---

 

 

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음에 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결합니다.(주로 배열에 있는 연속적인 값으로 문제를 해결해야할 때 사용합니다.)

투 포인터 알고리즘과 매우 유사 합니다.
2개의 포인터를 지정하면서 loop를 탐색하는 것이 핵심 포인트 입니다.^^

 

기본 개념을 그림으로 보면 다음과 같습니다.

그림으로 보면 쉬운것 같습니다.
그럼 슬라이딩 윈도우를 어떻게 구현하면 좋을까요?

예를 들어 [1, 2, 1, 3, 4, 5] 숫자들 중 연속적인 3개의 숫자의 합 중 최소 값을 구하려면 어떻게 할까요?

처음에는 배열 합을 구하여 그 값을 최솟값으로 저장 합니다.
그 다음에 start point, end point를 정하여 loop를 돌리며 최솟값인지 확인하면 됩니다.!

// 1. 배열의 합을 구한다.
// 2. start point, end point를 정해서 loop를 돌며 최솟값인지 확인

int winSize = 3; // 윈도우 사이즈
int arrSize = 6; // 배열의 크기

// 배열의 합을 구한다.
int min = 0; // 최솟값
for(int i = 0; i < winSize; i ++) {
    min += A[i]; 
}

int temp = min;

// start point, end point를 정해서 loop를 돌며 최솟값인지 확인
for(int endPoint = windSize; endPoint < arrSize; endPoint++) {
    int startPoint = endPoint - winSize;
    temp = temp - A[startPoint] + A[endPoint];
    min = Math.min(temp, min);
}

백준 12847

12847번: 꿀 아르바이트
개념 설명에서는 최솟값이였지만, 이번 문제는 최댓값을 구하는 문제 입니다.
위 개념을 이해하셨으면 쉽게 해결하셨을 것 입니다.^^

12847번: 꿀 아르바이트

 

저는 첫 시도에 해결하지 못했는데, 그 이유는 타입이 안맞아서 그랬습니다.
급여를 int로 설정하지 말고 long으로 설정해야 합니다.

✅  데이터 범위를 잘 확인 합시다..!

 

조건에서
월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일, 일을 할 수 있는 날 m (0 ≤ m ≤ n), 급여(0 < 급여 ≤ 1,000,000) 이기 때문 입니다.

 

풀이

public class Quiz12847 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 일(급여 배열의 크기)
        int n = Integer.parseInt(st.nextToken());
        // 일할수 있는 일수(윈도우 사이즈)
        int m = Integer.parseInt(st.nextToken());
        // 급여 배열
        st = new StringTokenizer(br.readLine());
        long[] money = new long[n];
        for(int i = 0; i < n; i++) {
            money[i] = Long.parseLong(st.nextToken());
        }
        // 첫 급여
        long max = 0;
        for(int i = 0; i < m; i++) {
            max += money[i];
        }

        /**
         * 슬라이딩 윈도우
         * max에서 기존의 것은 빼고, 새로운 값은 더한다.
         */
        long temp = max;
        for(int i = m; i < n; i++) {
            int j = i - m; // 3 - 3 = 0, 4 - 3 = 1
            temp = temp + money[i] - money[j];
            max = Math.max(temp, max);
        }

        System.out.println(max);
        br.close();
    }
}

백준 12891

12891번: DNA 비밀번호
내 힘으로 풀지 못했다…. ㅠ0ㅠ
조건을 어떠한 방식으로 구현해서 해결해야 하는지 감을 못잡았습니다.

12891번: DNA 비밀번호

 

풀이

public class Quiz12891 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int result = 0;
        int count = 0; // 4가되면 result 1증가

        // 문자열 길이
        int len = Integer.parseInt(st.nextToken());

        // 부분 문자열 길이
        int partLen = Integer.parseInt(st.nextToken());

        // 랜덤 문자열
        String str = br.readLine();

        // 필수 문자 갯수 배열
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[4];
        for (int i = 0; i < 4; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] == 0) count++;
        }

        int[] newArr = new int[4];
        char[] ch = str.toCharArray();
        for (int i = 0; i < partLen; i++) {
            switch (ch[i]) {
                case 'A':
                    newArr[0]++;
                    if (newArr[0] == arr[0]) count++;
                    break;
                case 'C':
                    newArr[1]++;
                    if (newArr[1] == arr[1]) count++;
                    break;
                case 'G':
                    newArr[2]++;
                    if (newArr[2] == arr[2]) count++;
                    break;
                case 'T':
                    newArr[3]++;
                    if (newArr[3] == arr[3]) count++;
                    break;
            }
        }

        if(count == 4) result++;

        /**
         * 슬라이딩 윈도우
         * i = start point
         * j = end point
         */
        for(int i = partLen; i < len; i++) {
            int j = i - partLen;
            // 윈도우 범위에 새롭게 들어간 값 추가
            switch (ch[i]) {
                case 'A':
                    newArr[0]++;
                    if (newArr[0] == arr[0]) count++;
                    break;
                case 'C':
                    newArr[1]++;
                    if (newArr[1] == arr[1]) count++;
                    break;
                case 'G':
                    newArr[2]++;
                    if (newArr[2] == arr[2]) count++;
                    break;
                case 'T':
                    newArr[3]++;
                    if (newArr[3] == arr[3]) count++;
                    break;
            }

            // 윈도우 범위에 벗어난 값 제거
            switch (ch[j]) {
                case 'A':
                    if (newArr[0] == arr[0]) count--;
                    newArr[0]--;
                    break;
                case 'C':
                    if (newArr[1] == arr[1]) count--;
                    newArr[1]--;
                    break;
                case 'G':
                    if (newArr[2] == arr[2]) count--;
                    newArr[2]--;
                    break;
                case 'T':
                    if (newArr[3] == arr[3]) count--;
                    newArr[3]--;
                    break;
            }
            if(count == 4) result++;
        }
        System.out.println(result);
    }
}