[Algorithm] Subsequence 판별하기

  오늘은 보다 간단한 상황에 대해서 공부해보자. 바로 Subsequence 판단 문제인데, Subsequence 의 정의는 아래와 같다.

https://en.wikipedia.org/wiki/Subsequence

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. - wiki

 

  배열이 주어졌다고 가정하면, 원소의 순서를 바꾸는 행위 없이 일부 원소만 delete 하여 origin array 로부터 subsequence 을 만들어낼 수 있다. 예를 들어 [1,5,7,9] 에 대해서 [1, 5], [1,7], [1,9], [5,7] 와 같은 subsequence 가 존재한다. 코딩테스트 문제에서 혹은 면접에서 origin array 와 candidate array 가 있을 때, candidate array 가 origin array 의 subsequence 인지 아닌지를 어떻게 판단할 수 있겠느냐고 물어볼 수 있다. 어떻게 해결할 수 있을까?

 

  솔루션은 단순하다. origin array 를 1번 순회하는 것만으로 판별이 가능하다. origin array 와 candidate array 의 position 을 나타내는 변수를 각각 array_idx, sequence_idx 라고 저장한 다음에 origin array 를 순회하면서 origin_array[array_idx] == candidate_array[sequence_idx] 라면 sequence_idx 를 하나 증가시킨다. origin_array 를 모두 순회하거나 sequence_idx 가 candidate_array.size() 와 같아지면 해당 loop 를 탈출한다. loop 를 탈출했을 때, sequence_idx == candidate_array_size() 라면 true 를, 다르다면 false 를 반환하여 subseuqence 인지 아닌지 판별하는 알고리즘을 간단하게 구현할 수 있다. 

 

  origin array 를 1회만 순회하면 되므로 시간 복잡도는 O(N) 이고, 공간 복잡도는 O(1) 이다.

 

[solution1]

using namespace std;

// time  : O(N)
// space : O(1)

bool isValidSubsequence(vector<int> array, vector<int> sequence) {
  // Write your code here.
  int array_idx = 0;
  int sequence_idx = 0;
  while(array_idx < array.size() && sequence_idx < sequence.size()){
    if(array[array_idx] == sequence[sequence_idx]){
      sequence_idx++;
    }
    array_idx++;
  }
  return sequence_idx == sequence.size();
}

[solution2]

using namespace std;

// time  : O(N)
// space : O(1)

bool isValidSubsequence(vector<int> array, vector<int> sequence) {
  // Write your code here.
  int sequence_idx = 0;
  for(int i = 0 ; i <array.size(); i++){
    if(sequence_idx == sequence.size())
      break;
    if(sequence[sequence_idx] == array[i])
      sequence_idx++;
  }
  return sequence_idx == sequence.size();
}

https://github.com/versatile0010/AlgoExpert

GitHub - versatile0010/AlgoExpert: Solutions to AlgoExpert Problems.