선형자료구조 - 배열

선형 자료구조

 

자료구조(Data Structure)

-자료를 효율적으로 관리하기 위한 구조

-목적에 맞게 사용한 좋은 자료구조는, 실행시간 단축 or/and 메모리 용량 절감 효과가 있다.

 

자료구조의 분류

-선형 자료구조 : 배열, 연결리스트, 스택, 큐, 데크, 해시 테이블

-비선형 자료구조 : 트리, 그래프, 힙/우선순위 큐, 트라이

 

자료구조의 구현

-추상 자료형 

  자료 형태와 자료에 대한 연산을 정의한 것

  구체적인 구현 방법은 명시하지 않음

 

배열(Array)

-많은 수의 데이터를 다룰 때 사용하는 자료구조

-각 데이터를 인덱스와 1:1 대응하도록 구성

-데이터가 메모리 상에 연속적으로 저장됨

 

배열의 장점

-인덱스를 잉요하여 데이터에 빠르게 접근 가능

 

배열의 단점

-데이터의 추가/삭제가 번거로운 편

-미리 최대 길이를 정해서 생성해야 함

-가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성

-데이터 삭제 시, 인덱스를 유지하기 위한 빈 공간 유지

 

1차원 배열

//1차원 배열
System.out.println("1차원 배열");
int[] arr = {1,2,3,4,5};
for(int item : arr) {
    System.out.println("item = " + item);
}

arr[1] = 100;
System.out.println(Arrays.toString(arr));

 

2차원 배열

//2차원 배열
System.out.println("2차원 배열");
int[][] arr2 = {{1,2,3}, {4,5,6}};
System.out.println(arr2[0][1]);

for(int[] row:arr2) {
    for(int item : row) {
        System.out.println("item = " + item);
    }
}

 

//ArrayList - 1차원, 2차원
System.out.println("== ArrayList ==");
ArrayList list1 = new ArrayList(Arrays.asList(1,2,3));
System.out.println(list1);
list1.add(4);
list1.add(5);
System.out.println("list1 = " + list1);
list1.remove(2);
System.out.println("list1 = " + list1);
list1.remove(Integer.valueOf(2));
System.out.println("list1 = " + list1);

 

배열의 데이터 삽입

//배열의 데이터 삽입
public void insertData(int index,int data){
    if(index < 0 || index > this.arr.length){
        System.out.println("index Error");
        return;
    }

    int[] arrDup = this.arr.clone();
    this.arr = new int[this.arr.length + 1];

    for(int i = 0; i < index; i++){
        this.arr[i] = arrDup[i];
    }

    for(int i = index; i < this.arr.length; i++){
        this.arr[i] = arrDup[i - 1];
    }

    this.arr[index] = data;
}

 

배열의 데이터 삭제

//배열에서 특정 데이터 삭제
public void removeData(int data){
    int targetIndex = -1;

    for(int i = 0; i < this.arr.length; i++){
        if(this.arr[i] == data) {
            targetIndex = i;
            break;
        }
    }
    if(targetIndex == -1){
        System.out.println("targetIndex Error");
    }else{
        int[] arrDup = this.arr.clone();
        this.arr = new int[this.arr.length - 1];

        for(int i = 0; i < targetIndex; i++){
            this.arr[i] = arrDup[i];
        }

        for(int i = targetIndex; i < this.arr.length; i++){
            this.arr[i] = arrDup[i + 1];
        }
    }
}

 

 

---

연습 문제1

배열 arr의 모든 데이터에 대해서 짝수 데이터들의 평균과 홀수 데이터들의 평균을 출력

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        float sumEven = 0;
        float sumOdd = 0;
        int evenCount = 0;
        int oddCount = 0;

        for(int item : arr){
            if(item % 2 == 0){
                sumEven += item;
                evenCount++;
            }else {
                sumOdd += item;
                oddCount++;
            }
        }
        System.out.println("Even AVG : " + sumEven / evenCount);
        System.out.println("Odd AVG : " + sumOdd / oddCount);
    }
}

 

연습문제 2

배열 arr에서 target에 해당하는 값의 인덱스를 출력 해당 값이 여러 개인 경우 가장 큰 인덱스 출력

해당 값이 여러 개인 경우 가장 큰 인덱스 출력

public class Main {
    public static void main(String[] args) {
        int [] arr ={1,1,100,1,1,1,100};
        int target = 100;
        int idxMax = -1;

        for(int i =0; i<arr.length; i++){
            if(arr[i] > target){
                if(i > idxMax){
                    idxMax = i;
                }
            }
        }
        if(idxMax >= 0){
            System.out.println(idxMax);
        }

    }
}

 

연습문제 3

배열 arr의 데이터 순서를 거꾸로 변경

추가 배열을 사용하지 않고 구현

public class Main {
    public static void main(String[] args) {
      int[] arr = {1,3,5,7,9};

      for(int i = 0; i <arr.length / 2; i++) {
          int tmp = arr[i];
          arr[i] = arr[arr.length - i - 1];
          arr[arr.length - i - 1] = tmp;
      }
      System.out.println(Arrays.toString(arr));
    }
}

 

연습문제 4 

배열 arr 에서 peek값 모두 출력  

public class Main {
    public static void main(String[] args) {
     int[] arr = {3,1,2,6,2,2,5,1,9,18,1,11};

     for(int i = 0; i<arr.length; i++) {
         if(i == 0 && arr[i] > arr[i + 1]){
             System.out.println(arr[i + 1] + "");
         }else if(i == arr.length - 1 && arr[i] > arr[i - 1]){
             System.out.println(arr[i] + "");
         }else{
             if(arr[i] > arr[i - 1] && arr[i] > arr[i + 1]){
                 System.out.println(arr[i] + "");
             }
         }
     }
     System.out.println();
    }
}