배열의 정의와 예제 문제

배열의 정의

• 배열(Array)는 동일한 자료형들을 하나로 묶어 관리할 수 있게 하는 자료구조이다.
• 일반적으로 배열은 인접한 메모리로 이어져 있다
  • 가령 예를 들자면 0x10 부터 시작하여 5개의 int형 요소들을 가지고 있는 배열 array을 만든다면 시작 주소는 0x10이고 마지막 주소는 0x23이 된다. C/C++ 에서 포인터에 대한 개념을 알고 있다면 이해하기 쉬울 것이다.
  • 그렇다면 배열을 선언한 배열 변수는 해당 배열의 첫 주소를 가리키고 있는 참조변수가 된다. 즉, array는 0x10메모리를 가리키고 있다는 것이다.
• 이렇게 인접한 메모리로 이어짐으로 인하여, 색인(index)를 사용한 임의 접근(RandomAccess)가 가능하고, 색인을 사용하여 데이터를 조회, 수정, 삽입, 삭제를 하는데 O(1)의 매우 강력한 성능을 가진다.
• 하지만 강력한 성능만큼 강력한 제약도 존재한다.
• 먼저 배열을 선언하여 크기를 지정한 시점에서 더 이상 그 배열의 크기를 늘리거나 줄일 수 없다. 즉 가변적으로 길이를 설정할 수 없으며 길이를 늘리거나 줄이려면 반드시 새로운 배열을 사용하여 수행할 수 밖에 없다.
• 이런 제약사항 때문에 배열을 사용할 때는 들어오는 데이터의 상한을 파악하는것이 중요하다. 상한을 잘못 알거나 모를 경우, 다시 배열을 지정하여 복사해야하는 시간적 코스트와 메모리 코스트가 지출되기 떄문이다.
  • 만약 상한이 계속해서 바뀌거나, 상한을 알 수 없을 경우, 배열보다는 연결리스트를 사용하는 것이 더 좋다.

 

 

 

배열을 사용한 예제 문제 - 최소 최대

https://www.acmicpc.net/problem/10818

10818번: 최소, 최대

• 해당 문제는 데이터를 받아 그 데이터 중 최대, 최소를 구하여 출력하는 문제이다.
• 배열의 첫 번째 요소들을 max와 min으로 잡고, 자신보다 큰 수가 존재한다면 max를 갱신, 자신보다 작은 수가 존재한다면 min을 갱신함으로서 O(N)으로 구현이 가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] data = new int[N];
        st = new StringTokenizer(br.readLine());

        int idx = 0;

        while(st.hasMoreTokens()){
            data[idx++] = Integer.parseInt(st.nextToken());
        }

        int max = data[0];
        int min = data[0];

        for(int element: data){
            max = Math.max(max, element);
            min = Math.min(min, element);
        }
        
        System.out.println(min + " " + max);
    }
}

 

 

 

배열을 사용한 예제 문제 - 나누어 떨어지는 숫자 배열

https://school.programmers.co.kr/learn/courses/30/lessons/12910

프로그래머스

• 입력으로 데이터가 들어있는 배열과, 기준이 되는 수 divisor가 들어온다. 이때 배열의 각 요소를 순회하며 divisor과 나누어 나머지가 0이라면 답안 배열에 추가하되, 답안 배열은 오름차순으로 정렬되어 있어야 한다는 문제이다.
• 해당 문제 역시 정렬을 하면 되는 문제이다. 이때 정렬하는 시점이 달라질 수 있다. 필자는 처음 입력으로 받은 배열을 먼저 정렬하는 방법을 선택하였다.
• 배열의 각 요소를 순회하며 divisor로 나누어 나머지가 0인지를 확인한다. 배열의 요소들이 오름차순으로 정렬되어 있기 때문에 divisor로 나누어 나머지가 0이라면 곧바로 답안 배열에 넣으면 된다.

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int divisor) {
        ArrayList<Integer> ans = new ArrayList<>();
        Arrays.sort(arr);
        int idx = 0;
        
        for(int element: arr){
            if(element % divisor == 0){
                ans.add(element);
                idx++;
            }
        }
        
        int[] answer;
        
        if(idx == 0){
            answer = new int[]{-1};
        } else{
            answer = new int[idx];
            for(int i = 0; i < ans.size(); i++){
                answer[i] = ans.get(i);
            }
        }
        
        return answer;
    }
}

• 만약 나누어 떨어지는수가 없다면 -1을 넣어 반환해야 하는 것에 유의하자.