[프로그래머스] 징검다리 건너기
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씩줄이는 것이 아니라 구간별로 나누어 생각하는 방법이 있었다.
'프로그래머스 > 카카오' 카테고리의 다른 글
[프로그래머스] 프렌즈 4블록 (0) | 2020.05.03 |
---|---|
[프로그래머스] [1차] 셔틀버스 (0) | 2020.04.28 |
[프로그래머스] 호텔 방 배정 (0) | 2020.04.22 |
[프로그래머스] 불량 사용자 (0) | 2020.04.22 |
[프로그래머스] 괄호변환 (0) | 2020.04.18 |