[자료구조] 배열(Array)

 

배열

• 같은 자료형을 담는 자료구조

 

배열 특징

• 삽입은 다른 숫자들을 오른쪽으로 옮기는 연산이 필요하다.
• 삭제는 다른 숫자들을 왼쪽으로 옮기는 연산이 필요하다. 같은 자료형만 담을 수 있다.
• 배열을 숫자를 담는 공간으로만 생각하지 말고, 배열의 인덱스를 이용해서도 논리적으로 문제를 풀 수 있다.

 

시간 복잡도

• 삽입 : O(n)
  • 오른쪽 시프트 연산을 한다. 최악의 경우 n번의 연산이 일어남.
• 삭제 : O(n)
  • 왼쪽 시프트 연산을 한다. 최악의 경우 n번의 연산이 일어남.
• 조회 : 1
  • 인덱스를 알고 있다면, 1번의 연산이 일어난다.

 

배열 구현

 

내 풀이

namespace 배열_구현
{
    public class Array
    {
        public static void insert(int idx, int num, int[] arr, int len)
        {
            for(int last_idx = arr.Length - 2; last_idx >= idx; last_idx--)
            {
                arr[last_idx + 1] = arr[last_idx];
            }
            arr[idx] = num;
        }

        public static void erase(int idx, int[] arr, int len)
        {
            for(int index = idx + 1; index <= arr.Length-1; index++)
            {
                arr[index - 1] = arr[index];
            }
            arr[arr.Length - 1] = 0;
        }

        public static void printArr(int[] arr, int len)
        {
            foreach(int number in arr)
            {
                Console.Write($"{number} ");
            }
            Console.WriteLine();
        }

        public static void insert_test()
        {
            Console.WriteLine("***** insert test *****");
            int[] arr = { 10, 20, 30, 0, 0, 0, 0, 0, 0, 0 };
            int len = 3;
            insert(3, 40, arr, len); // 10 20 30 40
            printArr(arr, len);
            insert(1, 50, arr, len); // 10 50 20 30 40
            printArr(arr, len);
            insert(0, 15, arr, len); // 15 10 50 20 30 40
            printArr(arr, len);
        }

        public static void erase_test()
        {
            Console.WriteLine("***** erase_test *****");
            int[] arr = { 10, 50, 40, 30, 70, 20, 0, 0, 0, 0 };
            int len = 6;
            erase(4, arr, len); // 10 50 40 30 20
            printArr(arr, len);
            erase(1, arr, len); // 10 40 30 20
            printArr(arr, len);
            erase(3, arr, len); // 10 40 30
            printArr(arr, len);
        }

        static void Main(string[] args)
        {
            insert_test();
            erase_test();
        }
    }
}

 

다른 사람 풀이 (C++)

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

void insert(int idx, int num, int arr[], int& len){
  for(int i = len; i > idx; i--) // 조건식이 i >= idx이면 런타임 에러 발생함. 
    arr[i] = arr[i-1];
  arr[idx] = num;
  len++;
}

void erase(int idx, int arr[], int& len){
  len--;
  for(int i = idx; i < len; i++)
    arr[i] = arr[i+1];
}

void printArr(int arr[], int& len){
  for(int i = 0; i < len; i++) cout << arr[i] << ' ';
  cout << "\n\n";
}

void insert_test(){
  cout << "***** insert_test *****\n";
  int arr[10] = {10, 20, 30};
  int len = 3;
  insert(3, 40, arr, len); // 10 20 30 40
  printArr(arr, len);
  insert(1, 50, arr, len); // 10 50 20 30 40
  printArr(arr, len);
  insert(0, 15, arr, len); // 15 10 50 20 30 40
  printArr(arr, len);
}

void erase_test(){
  cout << "***** erase_test *****\n";
  int arr[10] = {10, 50, 40, 30, 70, 20};
  int len = 6;
  erase(4, arr, len); // 10 50 40 30 20
  printArr(arr, len);
  erase(1, arr, len); // 10 40 30 20
  printArr(arr, len);
  erase(3, arr, len); // 10 40 30
  printArr(arr, len);
}

int main(void) {
  insert_test();
  erase_test();
}

 

 

연습문제

주어진 길이 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

func2({4, 13, 63, 87}, 4) = 1

 

 

내 풀이 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 배열_구현
{
    public class _0x01연습문제
    {
        public static int func2(int[] arr, int n)
        {
            // O(n^2)
            for(int i = 0; i < arr.Length; i++)
            {
                for(int j = i+1; j < arr.Length; j++)
                {
                    if (arr[i] + arr[j] == 100)
                    {
                        return 1;
                    }
                }
            }

            return 0;
        }

        public static void Main(string[] args)
        {
            int[] arr = { 4,13,63,87 };
            int n = 4;

            int result = func2(arr, n);
            Console.WriteLine($"{result}");
        }
    }
}

일일이 하나씩 비교하면서 합이 100인 두 원소가 존재하는지 확인해봤다. 

 

 

다른 사람 풀이

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 배열_구현
{
    public class _0x01연습문제
    {
        public static int func2(int[] arr, int n)
        {
            int[] arr2 = new int[200];
            for(int i = 0; i < arr.Length; i++)
            {
                if (arr2[100-arr[i]] == 1)
                {
                    return 1;
                }

                arr2[arr[i]] = 1;
            }

            return 0;
        }

        public static void Main(string[] args)
        {
            int[] arr = { 1,23,53,77,60 };
            int n = 5;

            int result = func2(arr, n);
            Console.WriteLine($"{result}");
        }
    }
}

배열의 인덱스를 이용한 풀이다. 

합이 100이 되는 값을 구하려면 100 - arr[i]를 하면 된다. 

100 - arr[i]가 있는지 없는지는 크기가 200인 arr2배열에 저장한다. 100 - arr[i]가 있으면 1을 반환하면 된다.