프로그래머스 레벨 2 - 퍼즐 게임 챌린지[자바]

문제

 

프로그래머스

 

풀이과정

 

배열의 어마어마한 길이를 보고 당연히 시간복잡도 때문에 안될줄 알면서도 순차적으로 돌며 체크해봤다. 생각이 안나서...

 

import java.util.*;
class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        //각 배열의 레벨별 증가값을 구하기
        //증가값 = (전 시간 + 현재시간) * 틀린횟수 + 현재시간
        int level = Arrays.stream(diffs)
            .min()
            .getAsInt();
        
        // {인덱스, [난이도, 전시간, 현재시간]} 맵
        Map<Integer, long[]> numMap = new HashMap<>();
        for(int i=0; i<diffs.length; i++) {
            if(i > 0) {
                numMap.put(i, new long[]{diffs[i], times[i-1], times[i]});    
            } else {
                numMap.put(i, new long[]{diffs[i], 0, times[i]});    
            }
            
        }
        
        while(true) {
            long time = 0;
            for(int key : numMap.keySet()) {
                long[] value = numMap.get(key);
                
                if(level >= value[0]) { // 레벨이 더 크면 현재의 시간만 뺀다. 
                    time += value[2];
                } else { // 아닐경우 추가시간
                    long wrongCount = value[0] - level;
                    time += (value[1] + value[2]) * wrongCount + value[2];
                }
                
                if(time > limit) {
                    time = limit+1;
                    break;
                }
            }
            
            if(time <= limit) break;
            
            level++;
        }
        return level;
    }
}

 

맵에다 하나의 작업에 대한 정보를 넣었다. 그리고 레벨 1부터 올려가면서 시간 계산하면서 리밋 타임보다 작아지는 시점에 리턴을 했다. 코드를 돌려보니 알고리즘 자체 문제는 없고 시간 초과 되는 문제가 발생했다.

 

그래서 끙끙 앓다가 이진 탐색을 사용하라는 힌트를 보고 정신이 벌떡 들어 왜 그 생각을 못한거지 라고 자책을 조금 하다가 다음날 멀쩡한 정신으로 다시 풀었다.

 

import java.util.*;
class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        //이진 탐색
        int maxValue = Arrays.stream(diffs).max().getAsInt(); //최대값
        int minValue = 1; //최소값
        int level = (maxValue + minValue) / 2; //중간값
        
        // 값이 하나도 없을때까지
        while (minValue <= maxValue) { 
            long time = calTime(diffs, times, level);
            // limit 보다 작으면 레벨을 -1해서 계산 후 크다면 리턴 작으면 최소값 포인트 이동, 크면 최대값 포인트 이동
            if(limit == time) {
                return level;
            } else if(limit > time) {
            	// 레벨 1에 대한 체크 꼭해주기	
                long nextTime = level == 1 ? limit+1 : calTime(diffs, times, level-1);
                //레벨이 높을수록 리밋은 내려간다.
                if(limit < nextTime) {
                    return level;
                } else {
                    maxValue = level-1;
                }
            } else {
                minValue = level+1;
            }
            
            level = (maxValue + minValue) / 2;
        }
        
        return -1;
    }
    
    private long calTime(int[] diffs, int[] times, int level) {
        long time = 0;
        for(int i=0; i<diffs.length; i++) {
            int levDiff = diffs[i] - level;

            if(levDiff <= 0) { //작거나 같으면 문제 난이도가 더 낮으므로 원래 시간만 써 해결
                time += times[i];
            } else {
                //증가값 = (전 시간 + 현재시간) * 틀린횟수 + 현재시간
                int preTime = i == 0 ? 0 : times[i-1]; 
                int nowTime = times[i];
                int addValue = (preTime + nowTime) * levDiff + nowTime;

                time += addValue;
            } 
        }
        
        return time;
    }
}

 

평범한 이진탐색에 calTime() 이라는 메소드가 추가됐다. 이는 레벨을 구했을때 해당 레벨의 시간이 리밋보다 작을 경우 이게 정답인건지, 그냥 막연히 작은 수인건지 판단할 방법이 없다. 그래서 원래 레벨-1을 해서 시간을 구해보고 그 값이 리밋보다 커진다면 해당 레벨이 정답인 것이다.

 

마지막으로 이렇게 해서 제출을 했더니 문제 14번만 틀리는 상황이 발생했다. 또 끙끙 앓다가 자세히 보니 레벨이 1일때 처리를 따로 해줘야 한다는 걸 알았다. calTime() 메소드를 호출할때 레벨-1을 매개변수로 넣는데  레벨이 1일경우 0이 되버려서 문제 조건에 맞지 않는 계산을 해버리게 된다. 레벨이 1보다 낮은 경우는 존재하지 않으므로 최소값 1을 리턴해주기 위해서 처리를 해주었다.(주석참조)

 

리팩토링

 

import java.util.*;
class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int maxValue = Arrays.stream(diffs).max().getAsInt();
        int minValue = 1;

        while (minValue < maxValue) { 
            int level = (maxValue + minValue) / 2;
            long time = calTime(diffs, times, level);
 
            if(limit >= time) {
                maxValue = level;
            } else {
                minValue = level+1;
            }
        }
        
        return maxValue;
    }
    
    private long calTime(int[] diffs, int[] times, int level) {
        long time = 0;
        for(int i=0; i<diffs.length; i++) {
            int levDiff = diffs[i] - level;
            
            if(levDiff <= 0) {
                time += times[i];
            } else {
                int preTime = i == 0 ? 0 : times[i-1]; 
                int nowTime = times[i];
                int addValue = (preTime + nowTime) * levDiff + nowTime;

                time += addValue;
            } 
        }
        
        return time;
    }
}

 

좀 더 코드를 다듬어 보았다. maxValue랑 limit을 비교해서 calTime() 메소드를 한번 더 태우는 것이 아닌 이진 탐색 내에서 모두 처리하고 마지막에 남은 maxValue가 답이 될 수 있도록 했다. 가독성 면에서 훨씬 좋아진 것을 알 수 있다.