[코드트리/NL] 연속부분수열일까 (w. 슬라이딩 윈도우 알고리즘)

✏️ 문제 설명

n1개의 원소로 이루어져 있는 수열 A의 정보와, n2개의 원소로 이루어져 있는 수열 B의 정보가 주어졌을 때 수열 B가 수열 A의 연속부분수열인지를 판단하는 프로그램을 작성해보세요.

수열 B가 수열 A의 원소들을 연속하게 뽑았을 때 나올 수 있는 수열이라면 연속부분수열이라 부릅니다.

예를 들어 수열 A가 [1, 5, 2, 6] 일때 수열 B가 [5, 2]라면 수열 B는 수열 A의 연속 부분 수열이지만, 만약 수열 B가 [5, 6]이라면 연속 부분 수열이 아닙니다.

 

---

✏️ code

💻 슬라이딩 윈도우 알고리즘

• 이거 왜 써야 돼?
  
  • 슬라이딩 윈도우 알고리즘은 배열, 리스트 데이터 구조에서 연속된 부분 배열의 합, 최대값 등을 효율적으로 계산하는데 사용합니다.
  • 왜 효율적일까? 반복적인 계산을 줄여 시간 복잡도를 낮출 수 있기 때문입니다.
  • 일반적으로 고정된 크기의 윈도우를 사용하여 데이터를 처리합니다.
  • 👉🏻 본 문제에서는 전체 배열을 반복적으로 탐색하는 대신, 현재 윈도우의 변화만 추적하는 방식으로 중복 계산을 최소화하고자 슬라이딩 윈도우 알고리즘을 사용했습니다.
• 슬라이딩 윈도우 알고리즘의 개념
  • 고정된 크기의 윈도우를 사용하여 데이터를 처리하는 알고리즘입니다.
  • 고정된 크기의 윈도우를 시작 부분으로 설정, 그 윈도우를 배열이나 리스트에서 한 칸씩 오른쪽으로 이동
  • 윈도우가 이동할 때마다, 윈도우에 포함된 요소들을 검사(필요한 작업 수행)
• 슬라이딩 윈도우 알고리즘의 예제
  • 최대 부분 배열 합
  • 고정된 크기의 부분배열 평균
  • 문자열의 아나그램 찾기
  • 주식 가격의 이동 평균 계산

 

📌 고민했던 부분

• isSubsequence 함수에서 슬라이딩 윈도우 알고리즘 적용
  • for (int i = 0; i <= n1 - n2; i++)
    • n1 - n2을 한 이유는 이 이상의 값으로 i가 넘어갈 경우, 어차피 n2 즉 arr2.length를 넘어서게 되기 때문입니다.
    • 넘을 경우 NullPointerException이 발생할 것으로 예상되었고, 이는 불필요한 계산이기도 하기 때문에 n1 - n2를 했습니다.
  • if (arr1[i+j] != arr2[j])
    
    • 입력값이 아래와 같은 경우
      4 2
      1 5 6 2
      5 6

i+j	j	비교 값
0+0	0	arr1[0] = 1 != arr2[0] = 5 true -> break
1+0	0	arr1[1] = 5 != arr2[0] = 5 false -> 계속 비교
1+1	1	arr1[2] = 6 != arr2[1] = 6 false -> 비교 종료

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        int arr1[] = new int[n1];
        int arr2[] = new int[n2];

        StringTokenizer st1 = new StringTokenizer(br.readLine().trim());
        for (int i = 0; i < n1; i++) {
            arr1[i] = Integer.parseInt(st1.nextToken());
        }
        StringTokenizer st2 = new StringTokenizer(br.readLine().trim());
        for (int i = 0; i < n2; i++) {
            arr2[i] = Integer.parseInt(st2.nextToken());
        }

        System.out.print(isSubsequence(arr1, arr2) ? "Yes" : "No");
        br.close();
    }

    private static boolean isSubsequence(int arr1[], int arr2[]) {
        int n1 = arr1.length;
        int n2 = arr2.length;

        for (int i = 0; i <= n1-n2; i++) {
            boolean match = true;

            for (int j = 0; j < n2; j++) {
                if (arr1[i+j] != arr2[j]) {
                    match = false;
                    break;
                }
            }

            if (match) {
                return true;
            } 
        }   
        return false;
    }
}

 

---

• 참고자료
  • https://f-lab.kr/insight/sliding-window-algorithm-20240516