티스토리 뷰

728x90

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

2019 카카오 개발자 겨울 인턴십 Level 3 문제다.

 

 

문제 설명에 나온 입출력 예시 처럼

무식하게 while문을 통해 징검다리를 1씩 감소시키는 방식으로 풀었었는데,

당연히 시간초과가 났다.

 

알고리즘을 풀면서 이분탐색을 많이 사용해본적이 없어서

어떤 문제에 이분탐색을 사용해야 하는지 캐치하지 못했던 것 같다.

결국 다른 분의 풀이를 참고했다.

 

어떤 징검다리를 4명이 건널 수 있다면,

징검다리의 값에서 1씩 4번 감소시키며 건널 수 있는지 확인하는 것과

아예 4를 한번 감소시켜 건널 수 있는지 확인하는 것과 동일하다. (당연하지만 생각해내지 못함...)

 

 

건널 수 있는 최소 인원과 최대 인원을 설정한 후 중간값을 구하고,

그 중간값이 다리를 건널 수 있다면 최소 인원을 증가,

건널 수 없다면 최대 인원을 감소시키고

최소 인원과 최대 인원이 엇갈릴 때까지 반복한다.

 

class Solution {
    public int solution(int[] stones, int k) {
    	int ans = 0;
        int min = 1, max = 200000000;
        
        while(min<=max) {
        	int mid = (min + max) / 2;
        	if(isToCross(mid, stones, k)) {
        		ans = Math.max(ans, mid);
        		min = mid + 1;
        	}
        	else
        		max = mid - 1;
        }
        
        return ans;
    }
    
    static boolean isToCross(int people, int[] arr, int k) {
    	int num = 0;

    	for(int i : arr) {
    		if(i - people < 0) 
    			num++; // 밟지 못하는 칸이 얼만큼 연속되는지 카운트
    		else 
    			num = 0;
    		if(k == num) // 한 번에 건널 수 있는 칸과 같으면 못 건너는 것 
    			return false;
    	}
    	return true;
    }

}

 

참고

https://velog.io/@topqr123q/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2019-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%9D%B8%ED%84%B4%EC%8B%AD-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%EA%B1%B4%EB%84%88%EA%B8%B0-by-Java

 

 

 

728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함