2.1.2.19 연속부분 수열 여부 판단하기

풀이1

• 130ms 10MB

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();
        int n2 = sc.nextInt();
        int[] a = new int[n1];
        int[] b = new int[n2];
        for (int i = 0; i < n1; i++)
            a[i] = sc.nextInt();
        for (int i = 0; i < n2; i++)
            b[i] = sc.nextInt();
        
        //
        for(int s = 0 ; s <= n1-n2; s++){
 
            if(a[s] != b[0]) continue;
 
            int bEndIdx = 0;
            int cnt = 0;
            for(int e=s; e<s+n2; e++){
                if(a[e]!=b[bEndIdx++]) break;
                else{
                    cnt++;
                }
                if(cnt==n2 && a[e]==b[n2-1]){
                    System.out.print("Yes");
                    return;
                }
            
            }
        }
        System.out.print("No");
        return;
    }
}

풀이1 - 틀렸던 부분

1. B 전체를 다 비교했는지 확인하지 않고, B의 마지막 값과 같으면 Yes 처리함.  
	- cnt를 활용하지 않음.
2. s + n2가 n1을 넘어가는 경우를 막지 않아서 배열 범위 초과가 발생함.
	- s < n1 으로 진행하였음. s <= n1-n2 로 범위 명확히 했어야 함.
	- 왜 s < n1-n2 가 아닌 s <= n1-n2 이냐면, 시작 지점이기 때문이다.

---

풀이2

• 134ms 10MB
• 함수 활용하는 것이 가독성측면에서 좋음.

import java.util.Scanner;
public class Main {
 
    static int n1,n2,a[],b[];
 
    static boolean isSame(int n){
        for(int s = 0 ; s < n2; s++){
            if(a[s + n] != b[s]){
                return false;
            }
        }
        return true;
    }
 
    static boolean isSubsequence(){
        for(int i = 0 ; i <= n1-n2; i++){
            if(isSame(i)){
                return true;
            }
        }
 
        return false;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n1 = sc.nextInt();
        n2 = sc.nextInt();
        a = new int[n1];
        b = new int[n2];
        
        for (int i = 0; i < n1; i++)
            a[i] = sc.nextInt();
        for (int i = 0; i < n2; i++)
            b[i] = sc.nextInt();
        
       if(isSubsequence()){
        System.out.print("Yes");
        return;
       }
       else{
        System.out.print("No");
        return;
       }
    }
}