[Algorithm] 배열 활용하기

개요

보통 배열은 데이터를 쌓아두는 용도로 사용한다.

배열을 다음과 같은 접근으로 생각하면 문제를 효율적으로 풀 수 있는 경우가 많다!

배열을 인덱스에 해당하는 원소를 빠르게 접근하는 목적으로 사용한다.

문장만 봐서는 뜻이 아리까리 하다.

예시 문제로 이해해보자.

두 원소의 합이 100

주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.

 

예시

func2({1, 52, 48}, 3) = 1,

func2({50, 42}, 2) = 0

 

문제를 봤을 때 O(N^2)의 시간복잡도를 가지는 풀이가 생각날 것이다.

배열을 순차적으로 순회하며 다른 모든 원소와 합이 100이 되는지 판별하면 된다.

하지만 위의 배열의 접근법을 활용하면 O(N)의 풀이를 할 수 있다.

#include<bits/stdc++.h>
using namespace std;

int func2(int arr[], int N) {
   int answer[101] = {};
   for (int i = 0; i < N; i++) {
      if (answer[100 - arr[i]] != 0)
         return 1;
      answer[arr[i]]++;
   }
   return 0;
}

코드를 보면 각 index에 해당하는 숫자가 배열에 등장했는지 빈도 수를 저장하고 현재 원소와 더하면 100이 되는 원소가 등장했었는지 확인하며 문제를 해결했다. 위의 경우 배열을 한번만 순회하면 되기 때문에 O(N)의 시간 복잡도를 가진다.

 

키 포인트

• 문제를 앞에 등장한 원소 중 더해서 100이 되는지 확인하는 문제로 재해석
• 등장여부를 배열에 저장하여 확인