[Programmers] #181922 - 수열과 구간 쿼리 4 [Java][C++][Python]

문제 링크

---

1. 아이디어

각 쿼리 [s, e, k]에 대해 s부터 e까지의 인덱스 i를 순회하면서 i가 k의 배수인 경우에만 arr[i]에 1을 더한다. 쿼리를 순서대로 처리하면서 arr를 직접 갱신하면 되므로 별도의 자료구조 없이 이중 반복문만으로 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times Q)$	$O(1)$

($N$ = arr의 길이, $Q$ = queries의 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        for (int[] q : queries) {
            int s = q[0];
            int e = q[1];
            int k = q[2];

            for (int i = s; i <= e; i++) {
                if (i % k == 0) arr[i]++;
            }
        }

        return arr;
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    for (auto& q : queries) {
        int s = q[0];
        int e = q[1];
        int k = q[2];

        for (int i = s; i <= e; i++) {
            if (i % k == 0) arr[i]++;
        }
    }

    return arr;
}

def solution(arr, queries):
    for s, e, k in queries:
        for i in range(s, e + 1):
            if i % k == 0:
                arr[i] += 1

    return arr

---

참고

제한사항에는 k의 범위가 $0 \le k \le 5$로 명시되어 있지만, 코드는 i % k로 나머지를 구해 k=0이 들어오면 정의되지 않은 동작(Java ArithmeticException, C++ 정의되지 않은 동작, Python ZeroDivisionError)이 발생한다. 문제 본문 어디에도 k=0일 때 어떻게 처리해야 하는지 명시되어 있지 않고 입출력 예에도 이 값이 등장하지 않아, 제한사항에 0을 포함시킨 것 자체가 문제 설계 과정의 오류일 가능성이 있다. 실제 채점 데이터가 이 케이스를 다루지 않아 위 코드로도 정답 처리되지만, 제한사항을 곧이곧대로 따르면 안전하지 않은 코드다.

---