[Programmers] PCCE 기출문제 10번 - 데이터 분석 - Java

문제

프로그래머스

 

풀이 

4개의 속성을 가지는 데이터가 있는데 하나의 속성에 대해 val_ext 보다 작은 값을 추출하고 sort_by 속성 오름차순으로 정렬하는 문제이다.

 

데이터가 500개이기때문에, 정렬을 하든, 선형으로 순회하든 상관이 없다.

 

1. HashMap을 이용해서 2차원 배열에 어떤 인덱스에 있는지 기록한다.

어차피 4개의 속성을 넣기도하고, 다른 풀이를 보면 List로 구현해서 찾으신 분들이 있었는데, HashMap을 사용하면, O(1)연산으로 찾을 수 있을 것이라고 생각했다.

 

2. ext 속성에 해당하는 val_ext 값이 작은 데이터를 ArrayList에 넣어준다.

 

3. 값을 answer 배열로 옮긴다.

 

4. 정렬해야할 속성에 대한 인덱스를 HashMap으로 가져온다.

 

5. 정렬을 수행하고 배열을 리턴한다.

 

근데 생각을 해보면, 데이터를 굳이 복사할 필요가 없이, data 배열에 어떤 속성의 값이 작았던 인덱스들만 ArrayList로 가지고 있고, 그것을 answer 배열에 가져오는 것이 효과적이라고 생각했다. 

그래서, 데이터를 복사한 풀이와 인덱스를 가지고 있는 풀이에 대한 소스코드 2개를 모두 첨부하겠다.

 

시간복잡도: O(500log(500))

 

소스코드

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private static final String CODE = "code";
    private static final String DATE = "date";
    private static final String MAXIMUM = "maximum";
    private static final String REMAIN = "remain";
    
    public int[][] solution(int[][] data, String ext, int val_ext, String sort_by) {
        HashMap<String, Integer> map = new HashMap<>();
        
        map.put(CODE, 0);
        map.put(DATE, 1);
        map.put(MAXIMUM, 2);
        map.put(REMAIN, 3);
        
        ArrayList<int[]> arr = new ArrayList<>();
        
        int tIdx = map.get(ext);
        
        for (int i = 0; i < data.length; i++) {
            if (data[i][tIdx] < val_ext) {
                arr.add(new int[] {data[i][0], data[i][1], data[i][2], data[i][3]});
            }
        }
        
        int[][] answer = new int[arr.size()][4];
        
        for (int i = 0; i < arr.size(); i++) {
            answer[i][0] = arr.get(i)[0];
            answer[i][1] = arr.get(i)[1];
            answer[i][2] = arr.get(i)[2];
            answer[i][3] = arr.get(i)[3];
        }
        
        int sIdx = map.get(sort_by);
        
        Arrays.sort(answer, (a1, a2) -> {
            return a1[sIdx] - a2[sIdx];
        });
        
        return answer;
    }
}

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private static final String CODE = "code";
    private static final String DATE = "date";
    private static final String MAXIMUM = "maximum";
    private static final String REMAIN = "remain";
    
    public int[][] solution(int[][] data, String ext, int val_ext, String sort_by) {
        HashMap<String, Integer> map = new HashMap<>();
        
        map.put(CODE, 0);
        map.put(DATE, 1);
        map.put(MAXIMUM, 2);
        map.put(REMAIN, 3);
        
        ArrayList<Integer> arr = new ArrayList<>();
        
        int tIdx = map.get(ext);
        
        for (int i = 0; i < data.length; i++) {
            if (data[i][tIdx] < val_ext) {
                arr.add(i);
            }
        }
        
        int[][] answer = new int[arr.size()][4];
        
        int idx = 0;
        
        for (int i : arr) {
            answer[idx][0] = data[i][0];
            answer[idx][1] = data[i][1];
            answer[idx][2] = data[i][2];
            answer[idx][3] = data[i][3];
            
            idx++;
        }
        
        int sIdx = map.get(sort_by);
        
        Arrays.sort(answer, (a1, a2) -> {
            return a1[sIdx] - a2[sIdx];
        });
        
        return answer;
    }
}

 

실행결과

 

시간 11.26% 개선되었고, 메모리를 약 4%개선했다.