코드트리: 함수를 이용한 연속부분수열 여부 판단하기

 

 

---

 

문제

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

 

 

 

 

실행 결과

 

 

 

 

코드(c++)

#include <iostream>
using namespace std;

bool isSubsequence(int arrA[], int a, int arrB[], int b) {
  for (int start = 0; start <= a - b; start++) {
    bool match = true;
    for (int i = 0; i < b; ++i) {
      if (arrA[start + i] != arrB[i]) {
        match = false;
        break;  
      }
    }
    if (match)
      return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int a, b;
  cin >> a >> b;  

  int arrA[100], arrB[100]; 

  for (int i = 0; i < a; i++) {
    cin >> arrA[i];
  }
  for (int i = 0; i < b; i++) {
    cin >> arrB[i];
  }

  if (isSubsequence(arrA, a, arrB, b)) {
    cout << "Yes";
  } else {
    cout << "No";
  }

  return 0;
}

 

 

 

 

코드 설명

isSubsequence 함수는 수열 B가 수열 A의 연속 부분수열인지를 판단하는 함수이다.

해당 함수는 이중 반복문을 사용해 B를 ( b - a) - start만큼 비교한다.

• 시작 인덱스(start)를 선언한다. start가 0에서 a - b 가 될 때까지 B가 A의 연속부분수열로 존재하는지 확인한다.
• B는 A의 부분 수열이므로 B의 모든 원소가 A의 해당 위치의 원소와 일치하는지 확인한다.
• 만약 모든 원소가 일치한다면(arrA[start + i] == arrB[i]), true를 리턴한다.
• 그렇지 않다면(arrA[start + i] != arrB[i]), 반복문에서 빠져나와 false를 반환한다.

 

---

 

문제 출처:

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석