Post

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

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

문제 링크


1. 아이디어

쿼리마다 $s$부터 $e$까지의 $i$를 확인해 $i$가 $k$의 배수일 때만 arr[i]에 1을 더한다. 배수를 따지는 대상은 원소 값이 아니라 인덱스 $i$이고, 0은 모든 양의 정수의 배수라 인덱스 0이 구간에 있으면 항상 더해진다. 제한사항은 $0 \le k \le 5$로 $k = 0$을 허용하지만 지문은 이 경우의 처리를 정하지 않았고 예제에도 나오지 않는다. 코드는 $k = 0$을 따로 처리하지 않으므로 이 입력에서는 i % k가 0으로 나누는 연산이 된다.


2. 코드

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        for (int[] q : queries) {
            int s = q[0], e = q[1], k = q[2];

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

        return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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], e = q[1], k = q[2];

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

    return arr;
}
1
2
3
4
5
6
7
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

This post is licensed under CC BY 4.0 by the author.