알고리즘 문제 풀이 - 배열 조각하기

문제 설명

정수 배열 arr와 query가 주어집니다.

query를 순회하면서 다음 작업을 반복합니다.

짝수 인덱스에서는 arr에서 query[i]번 인덱스를 제외하고 배열의 query[i]번 인덱스 뒷부분을 잘라서 버립니다.
홀수 인덱스에서는 arr에서 query[i]번 인덱스는 제외하고 배열의 query[i]번 인덱스 앞부분을 잘라서 버립니다.
위 작업을 마친 후 남은 arr의 부분 배열을 return 하는 solution 함수를 완성해 주세요.

제한사항

5 ≤ arr의 길이 ≤ 100,000
0 ≤ arr의 원소 ≤ 100
1 ≤ query의 길이 < min(50, arr의 길이 / 2)
query의 각 원소는 0보다 크거나 같고 남아있는 arr의 길이 보다 작습니다.

---

문제 접근 방법 - 1

-. 주어진 내용 그대로 인덱스를 돌아가며 정수 배열을 자른다.
-. 배열을 자르기 위해 리스트로 변경하여 쿼리를 진행한다.
-. 완성 후 다시 정수 배열로 변경한다.

완성 코드 - 1

public class Test_214_SculptingArr {
    public int[] solution(int[] arr, int[] query) {
        List<Integer> arrList = new ArrayList<>();

        for (int j : arr) {
            arrList.add(j);
        }

        for (int i = 0; i < query.length; i++) {
            if (i % 2 == 0) {
                arrList = new ArrayList<>(arrList.subList(0, query[i] + 1));
            } else {
                arrList = new ArrayList<>(arrList.subList(query[i], arrList.size()));
            }
        }

        int[] answer = arrList.stream().mapToInt(Integer::intValue).toArray();

        return answer;
    }
}

위 코드로도 작동은 되지만 효율적인 코드가 아니므로 수정

---

문제 접근 방법 - 2

-. 리스트를 자르는 것은 불필요한 객체를 만들게되므로 메모리 낭비가 심하기 때문에 Arrays.copyOfRange()를 사용해서 배열을 복사

완성 코드 - 2

public class Test_214_SculptingArr {
    public int[] solution(int[] arr, int[] query) {
		int start = 0;
        int end = arr.length;

        for (int i = 0; i < query.length; i++) {
            if (i % 2 == 0) {
                end = start + query[i] + 1;
            } else {
                start += query[i];
            }
        }

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