[프로그래머스, 12984] [level 4] 지형 편집 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/12984#

프로그래머스

728x90

---

메모리: 63.4 MB, 시간: 80.51 ms

사용 알고리즘: 구현

 

같은 층을 가진 칸이 몇 개가 있는지 구하여,

층을 기준으로 오름차순 정렬한다.

 

가장 낮은 층부터 가장 높은 층까지 층을 높여가며

해당 층을 만들기 위해 쌓아야 하는 블럭 수와 제거해야 하는 블럭 수를 계산해 준다.

답과 현재 비용을 비교하여 더 작은 값을 답에 저장해 준다.

 

원래 같은 층을 가진 칸이 몇 개가 있는지 구하기 위해TreeMap을 사용해 봤는데 효율성 4번이 시간 초과가 났다.

TreeMap 대신 HashMap을 사용한 후,

값을 꺼내 ArrayList에 담고 sort하는 방식으로 바꿨는데도 효율성 4번이 시간 초과가 났다.

Map이 시간복잡도는 O(1)이라곤 해도 실제 메모리에 접근하는 시간 때문에 좀 느리다고 알고 있어 Map 대신 배열을 사용했다.

land를 1차원 배열로 만들고 정렬한 후, 층의 개수를 구해주었다.

이렇게 해주니 효율성 4번이 통과했다.

import java.util.*;

public class Solution {
    public long solution(int[][] land, int P, int Q) {
        
        long up = 0; // 쌓아야 하는 블럭 개수
        long down = 0; // 제거해야 하는 블럭 개수
        
        // land를 1차원 배열로
        int[] landBy1th = new int[land.length * land.length];
        for(int i = 0; i < land.length; i++) {
            for(int j = 0; j < land[i].length; j++) {
                down += land[i][j];
                landBy1th[land.length * i + j] = land[i][j];
            }
        }
        // 1차원 배열로 만든 land 정렬
        Arrays.sort(landBy1th);
        
        // 같은 층을 가진 칸 개수 구하기
        ArrayList<int[]> blockInfo = new ArrayList<>();
        for(int i = 0; i < landBy1th.length; i++) {
            if(blockInfo.size() > 0
               && blockInfo.get(blockInfo.size() - 1)[0] == landBy1th[i]) {
                blockInfo.get(blockInfo.size() - 1)[1]++;
            }
            else {
                blockInfo.add(new int[] {landBy1th[i], 1});
            }
        }
        
        int under = 0; // 기준 높이보다 낮은 칸 개수
        int now = 0; // 기준 높이에 해당하는 칸 개수
        int top = land.length * land.length; // 기준 높이보다 높은 칸 개수
        
        int preHeight = 0; // 이전 기준 높이
        int height;
        
        long answer = Long.MAX_VALUE;
        for(int i = 0; i < blockInfo.size(); i++) {
            
            height = blockInfo.get(i)[0];
            
            // 기준 높이보다 낮은 칸 개수
            under += now;
            // 기준 높이에 해당하는 칸 개수
            now = blockInfo.get(i)[1];
            
            // 기준 높이 변화로 더 쌓거나 제거해야 하는 블럭 개수 수정
            up += (long)(height - preHeight) * under;
            down -= (long)(height - preHeight) * top;
            
            answer = Math.min(answer, up * P + down * Q);
            
            // 기준 높이보다 높은 칸 개수
            top -= now;
            
            preHeight = height;
        }

        return answer;
    }
}