https://school.programmers.co.kr/learn/courses/30/lessons/64062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
처음에 이 문제를 보자마자 while문을 돌리면서 단순히 밟은 디딤돌을 -1 해주는 식으로 코드를 짰더니 testcase는 정답이였지만 어마어마한 시간 초과가...
그래서 이분탐색으로 경로 변경함. 처음에 건널 수 있는가? < 라는 boolean 값을 변수로 선언했는데 자꾸만 답이 3이 아니라 4가 나오거나 시간 초과가 뜨는 것이다... 코드 짜임새도 요상하고 길어지기만 해서 새로운 boolean형 함수를 선언해서 건널 수 있다 / 없다의 값만 받아오도록 코드를 수정했다.
class Solution {
/*
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones
디딤돌의 최대 칸수 k
최대 몇 명까지 징검다리를 건널 수 있는지 answer
*/
static boolean isPossible(int stones[], int howmany, int k){
int count = 0;
for(int i = 0; i < stones.length; i++){
if(stones[i] < howmany){ //못 건넘
count++;
} else {
count = 0; //count 초기화
}
if(count == k){
return false;
}
}
return true;
}
public int solution(int[] stones, int k) {
int answer = 0;
// Arrays.sort(stones); 순서대로 건너야하니 sort하면 안될듯.
int min_friends = 1;
int max_friends = Integer.MAX_VALUE; // 친구들 수
// int count = 0; //건너뛴 디딤돌
// boolean isPossible = true;
while(min_friends <= max_friends){
int howmany = (min_friends + max_friends) / 2;
if(isPossible(stones, howmany, k)){
min_friends = howmany + 1;
answer = Math.max(answer, howmany);
}
else{
max_friends = howmany - 1;
}
}
return answer;
}
}
'Algorithms > programmers' 카테고리의 다른 글
[Hash] Lv.1 폰켓몬, 완주하지 못한 선수 (0) | 2024.03.04 |
---|---|
[Binary Search Tree] 길 찾기 게임 (0) | 2024.02.29 |
[이분탐색] 프로그래머스 입국심사 (0) | 2024.01.11 |
[Greedy] 프로그래머스 체육복, 큰 수 만들기, 구명보트, 단속카메라 (1) | 2023.12.28 |
[Dynamic Programming] 프로그래머스 정수삼각형 (0) | 2023.12.26 |