[프로그래머스/181893] 배열 조각하기

21 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이
  • 두 번째 풀이
• ☑️ 문법 정리 - Array 복사
  • Arrays.copyOf
  • Arrays.copyOfRange

☑️ 문제

프로그래머스 181893

☑️ 풀이

첫 번째 풀이

• List 에 arr의 원소들을 넣고, remove() 메서드를 사용해 잘라서 버려야 하는 구간을 삭제한 뒤 최종적으로 남은 원소들을 리턴했다.
• List 의 크기를 줄이고 재배열하기 때문에 시간복잡도가 O(n)에 가깝고, 이 작업이 계속되어 전체 시간 복잡도가 커져버렸다.

//시간: 154.01ms
//메모리: 79.4MB

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int[] query) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }

        for (int i = 0; i < query.length; i++) {
            if (i % 2 == 0) {
                for (int j = list.size() - 1; j > query[i]; j--) {
                    list.remove(j);
                }
            } else {
                for (int j = query[i] - 1; j >= 0; j--) {
                    list.remove(j);
                }
            }
        }

        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

두 번째 풀이

• 다른 사람들의 풀이를 보고 다시 풀어보았다.
• 원소를 바로 삭제하는 게 아닌, 반복문에서 배열의 시작과 끝 인덱스를 조정한다.
• 최종 인덱스에 맞춰 배열을 한 번에 잘라내기 때문에 훨씬 더 빨라졌다.
• Arrays.copyOfRange()를 사용하면 범위를 지정해서 배열을 리턴할 수 있다.

//시간: 8.77ms
//메모리: 88.5MB

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int[] query) {
        int start = 0;
        int end = 0;
        for (int i = 0; i < query.length; i++) {
            if (i % 2 == 0) {
                end = start + query[i];
            } else {
                start += query[i];
            }
        }

        return Arrays.copyOfRange(arr, start, end + 1);
    }
}

☑️ 문법 정리 - Array 복사

Arrays.copyOf

• Arrays의 메서드를 활용해서 배열을 복사한다.
• Arrays.copyOf(복사할 배열, 새 배열의 길이)
• 배열의 길이를 늘리면, 추가된 부분은 정수형의 경우 0, 객체는 null로 채워진다.
• 배열의 길이를 줄이면, 앞쪽에서부터 지정된 길이만큼 복사된다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] original = {1, 2, 3, 4, 5};

        int[] copy = Arrays.copyOf(original, original.length);
        System.out.println(Arrays.toString(copy)); // [1, 2, 3, 4, 5]
        
        int[] expandedCopy = Arrays.copyOf(original, 8);
        System.out.println(Arrays.toString(Arrays.toString(expandedCopy); // [1, 2, 3, 4, 5, 0, 0, 0]
    }
}

Arrays.copyOfRange

• 배열의 특정 구간을 복사하여 새 배열을 생성한다.
• Arrays.copyOfRange(원본 배열, 시작 인덱스, 끝 인덱스);
• 복사하려는 배열의 시작 인덱스는 포함되지만, 끝 인덱스는 포함된지 않는다.
• 끝 인덱스가 배열 길이를 초과하면 정수형의 경우 0, 객체는 null로 채워진다.
• 시작 인덱스가 음수이거나, 시작 인덱스가 끝 인덱스보다 크면 ArrayIndexOutOfBoundsException이 발생한다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] original = {10, 20, 30, 40, 50};

        int[] copy = Arrays.copyOfRange(original, 1, 4);
        System.out.println(Arrays.toString(copy)); // [20, 30, 40]
        int[] extendedCopy = Arrays.copyOfRange(original, 0, 7); // [10, 20, 30, 40, 50, 0, 0]
    }
}