[프로그래머스 기초_java] 수열과 구간 쿼리 1

Solution 1)  내 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }

        for (int[] tmp : queries) {
            for (int i = tmp[0]; i <= tmp[1]; i++) {
                list.set(i, list.get(i) + 1);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

Soltuon 2) 다른 사람의 풀이

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = {};

        for(int i=0; i<queries.length; i++){
            for(int j=queries[i][0]; j<=queries[i][1]; j++){
                arr[j]++;
            }
        }
        return arr;
    }
}

코드 및 문제 리뷰

2차원배열 queries의 각 요소가 배열의 인덱스 범위가 된다. 

해당 범위내에 있는 배열내의 요소들은 +1 시킨다.

[0, 2] 라면 배열의 0 ~ 2 까지 (idx 0, 1, 2의 요소)의 요소들을 +1 시키는 문제이다.

 

나는 List를 사용했으나 다른 풀이를 보면 기존의 arr 배열을 그대로 활용하는 것을 볼 수 있다.

시간복잡도 상에서 코드를 분석한다면 다른 사람의 풀이가 더 낫다. (추가 형변환, 즉 오버헤드의 발생이

필요 없기 때문)

 

아직까지 풀이하는 문제들은 시간복잡도나 공간복잡도 관점에서 후하기 때문에 문제 없지만,

추후를 생각하면 더 효율이 좋은 쪽으로 길을 들여 놓는 게 좋겠다.