Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열 구하기 – C++ 풀이

임의의 크기를 가진 정수 배열이 주어졌을 때, 인접한 요소 간의 차이가 0 또는 1이 되도록 요소들을 선택하는 부분 수열(subsequence) 중 가장 긴 것의 길이를 구하는 것이 과제입니다. 여기서 부분 수열이란 배열에서 원소들의 상대적인 순서를 유지하면서 일부 원소를 생략하여 만든 수열을 의미합니다.

예제 입력 및 출력

입력 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }

출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열의 길이: 3

설명 − 배열에서 순서를 유지하면서 {5, 6, 7}과 같은 부분 수열을 선택하면 인접 요소 간의 차이가 모두 1이 됩니다. 따라서 최대 길이는 3입니다.

입력 − int arr[] = { 2, 1, 7, 6, 5 }

출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열의 길이: 3

설명 − 인접 요소 간의 차이가 1인 부분 수열은 {7, 6, 5}입니다. 따라서 최대 길이는 3입니다.

프로그램에 사용된 접근 방식

  • 양수와 음수 요소를 모두 포함할 수 있는 정수형 배열을 입력받습니다.

  • 배열의 크기를 계산한 뒤, 배열과 크기를 함수에 전달하여 이후 작업을 수행합니다.

  • 임시 변수 maximum을 0으로 초기화하고, 루프 인덱스로 사용할 임시 변수 i 역시 0으로 초기화합니다.

  • unordered_map 타입의 변수 un_map을 생성합니다. 이 맵에는 각 값까지 이어지는 부분 수열의 길이가 저장됩니다.

  • i가 size보다 작은 동안 while 루프를 실행합니다.

  • 루프 내부에서 len을 0으로 설정한 후, 현재 값(arr[i])을 기준으로 다음 세 가지 조건을 순서대로 확인합니다.

  • un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]이면 len = un_map[arr[i]-1]로 갱신합니다.

  • un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]이면 len = un_map[arr[i]]로 갱신합니다.

  • un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]이면 len = un_map[arr[i]+1]로 갱신합니다.

  • 그다음 un_map[arr[i]] = len + 1로 설정합니다. 즉, 현재 값으로 끝나는 부분 수열의 최대 길이에 1을 더해 저장하는 것입니다.

  • maximum이 un_map[arr[i]]보다 작으면 maximum 값을 un_map[arr[i]]로 갱신합니다.

  • i 값을 1 증가시킵니다.

  • 루프가 종료되면 maximum을 반환하고 결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//최대 부분 수열의 길이를 계산하는 함수
int maximum_adj(int arr[], int size){
   int maximum = 0, i = 0;
   unordered_map<int, int> un_map;
   while(i < size){
      int len = 0;
      if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
         len = un_map[arr[i]-1];
      }
      if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
         len = un_map[arr[i]];
      }
      if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
         len = un_map[arr[i]+1];
      }
      un_map[arr[i]] = len + 1;
      if (maximum < un_map[arr[i]]){
         maximum = un_map[arr[i]];
      }
      i++;
   }
   return maximum;
}
int main(){
   int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum length subsequence with difference between adjacent elements as either 0
   or 1 are: "<< maximum_adj(arr, size);
   return 0;
}

실행 결과

Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4

복잡도 분석

이 알고리즘은 배열의 각 원소를 한 번씩만 방문하며, 각 원소에 대해 해시 맵 조회와 갱신 작업만 수행하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 배열에 등장하는 서로 다른 값의 개수에 비례하므로 최악의 경우 O(n)입니다. 이처럼 unordered_map(해시 맵)을 활용하면 이중 반복문을 사용하는 완전 탐색 방식(O(n²))보다 훨씬 효율적으로 문제를 해결할 수 있습니다.