[프로그래머스] 징검다리 건너기

2020. 4. 24. 17:05프로그래머스/카카오

 

import java.util.*;

class Solution {
    Map<Integer, Integer> nextStone = new HashMap<>();
    
    public int solution(int[] stones, int k) {
        int answer = 0;
        boolean endFlag = false;
        
        initStone(stones);
        while(true){
        for(int i=0; i<stones.length; ){
            if(nextStone.get(i)-i > k) {
                endFlag=true;
                break;
            }
            
            stones[i]--;
            
            if(stones[i]==0){
                updateNextStone(stones,i);
            }
            i=nextStone.get(i);
        }
        
         if(endFlag == true){
            break;
            } else {
            answer ++;
         }
        }
        return answer;
    }
    
    private void initStone(int[] stones){
        for (int i=0; i<stones.length; i++){
            nextStone.put(i,i+1);
        }
    }
    
    private void updateNextStone(int[] stones, int target) {
        for (int stone : nextStone.keySet()) {
            if(nextStone.get(stone) == target) {
                nextStone.put(stone,nextStone.get(target));
            }
        }
    }
    
}

돌마다, 다음 탐색해야할 돌이 어디인지  map을 통해 저장한다.

로직은 맞는듯 하지만 효율성 테스트를 통과하지 못하였다. 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int solution(int[] stones, int k) {
        int answer = Integer.MAX_VALUE;

        for(int i=0; i<=stones.length-k; i++){
            int temp = i;
            int stone = stones[i];
            
            for(int j=i; j<i+k; j++){
                if(stones[j]>stone){
                    stone=stones[j];
                    temp = j;
                }
            }
            if(answer>stone){
                answer = stone;
            }
            i = temp;
        }
        return answer;
    }

}

임의의 i번째부터 k개의 갯수중 최댓값만큼은 그 구간을 건널 수 있다는 것을 이용하여,

stone에 적힌 수를 1씩줄이는 것이 아니라 구간별로 나누어 생각하는 방법이 있었다.