[자바] 프로그래머스 - 수열과 구간 쿼리 4 (Lv0, Java)

목차

• 문제 : Programmers - 수열과 구간 쿼리 4
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : Programmers - 수열과 구간 쿼리 4

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘

• 구현
  
  • 문제에서 제시된 대로 구현해주면 됩니다.

 

풀이

  문제에서 제시된대로 구현해주면 된다. 별다른 알고리즘 없이 그냥 배열순회만 사용해 풀어도, 총 1000개의 쿼리에 대해 각 O(arr의 길이)만큼 필요하므로, O(1000^2)으로 풀 수 있다.

 

  예를들어 [2, 2, 4, 5, 4]가 query [0, 3, 3]을 통해 [3, 2, 4, 6, 4]로 바뀌는 과정은 아래와 같다.

 

  이하 코드는 약간 효율성을 더하기 위해 인덱스 s부터 e까지 모두 순회하지 않고,

 

1. s이상이면서 k의 배수인 가장 작은 수를 우선 찾고

int i = s/k*k;
if (s%k != 0) i+=k;

 

2. 이후 k만큼 증가하면서 배열을 순회한다.

while (i <= e) {
    arr[i]++;
    i+=k;
}

 

  하지만 그냥 s부터 e까지 하나씩 직접 순회해도 통과 가능한 문제이다.

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        for (int[] query : queries) {
            int s = query[0];
            int e = query[1];
            int k = query[2];

            if (k == 0) {
                if (s==0) arr[0]++;
                continue;
            }

            int i = s/k*k;
            if (s%k != 0) i+=k;
            
            while (i <= e) {
                arr[i]++;
                i+=k;
            }
        }

        return arr;
    }
}