[Programmers 코딩 기초 트레이닝 : Java] 수열과 구간 쿼리 4

🔗 문제 링크

프로그래머스 181922 - 수열과 구간 쿼리 4

---

💡 문제 요약

• 정수 배열 arr과 2차원 배열 queries가 주어집니다.
• 각 쿼리 [s, e, k]에 대해
  s ≤ i ≤ e인 인덱스 중 i가 k의 배수인 원소에 1을 더합니다.
• 모든 쿼리를 순차적으로 적용한 뒤의 결과 배열을 반환합니다.

예시
arr = [0, 1, 2, 3, 4], queries = [[0, 4, 1], [0, 3, 2], [0, 3, 3]]
결과: [3, 3, 4, 4, 5]

---

🧩 내가 작성한 코드

 

import java.util.Arrays;

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = Arrays.copyOf(arr, arr.length);
        
        for(int[] query : queries) {
        
            int start = query[0];
            int end = query[1];
            int k = query[2];
            
            for(int i=start; i<=end; i++) {
                if(i % k == 0) {
                    answer[i] ++;
                }
            }
        }
        
        return answer;
    }
}

---

💬 풀이 설명

1. 배열 복사 (Arrays.copyOf)
   • 원본 배열 arr을 직접 수정하지 않기 위해 answer 배열을 복사 생성합니다.
   • 이렇게 하면 원본 데이터 보존이 가능합니다.
2. 이중 반복문 구조
   • 바깥 반복문 → 각 쿼리 순회
   • 안쪽 반복문 → s부터 e까지 확인
   • i % k == 0이면 해당 인덱스에 +1 수행
3. 시간 복잡도
   • O(Q × N)
   • Q = 쿼리 개수, N = 배열 길이
   • 제한이 크지 않다면 충분히 효율적인 구조입니다.

---

 

⚙️ 성능 분석

항목내용

시간 복잡도	O(Q × N)
공간 복잡도	O(N) (복사 배열 사용)
효율성	단순 반복문으로 명확하며, N ≤ 1,000 수준 문제에서는 최적

---

🧩 요약

• Arrays.copyOf()로 원본 보존
• 단순 반복문으로 구현해 명확하고 디버깅 쉬움