[2019 카카오 개발자 겨울 인턴쉽] 징검다리 건너기 for JAVA

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

프로그래머스

[문제 설명]

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

---

[입출력 예]

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

 

[풀이]

1. 효율성 통과를 제외한 테스트 풀이 

 - 건너려는 사람이 무한 -> 이번 건너는 사람이 건널 수 있는지 없는지 파악하여 반복문 종료. while문 사용

 

 - 다음 사람은 이전 사람이 다 건너고 건널 수 있다. -> 한 사람당 stones 길이에 해당하는 for문 하나 사용

 

 - 중간에 0이 나타나면 -> 0이 k만큼 나타나면 건너지 못하는 것이므로 0이 k개만큼 나오는지 확인하는 for문 사용

 

처음부터 순서대로 건너는 사람을 파악하는 방법이다. 처음 구상했을 때는 효율성에 막혀 https://tech.kakao.com/2020/04/01/2019-internship-test/ 을 참고하여 아래와 같이 조건에 맞게 해결했다.

 

2. 효율성 포함 통과 풀이
 - result를 기준으로 이분 탐색 -> 최솟값 최댓값을 정하고 중간값을 m으로 초기화

 

 - m번째 사람이 건너려고 시도하면 이미 stones의 요소들은 m-1만큼 감소된 이후 -> stones의 요소가 m보다 작거나 같으면 0으로 만들어줌.     ex) m = 3,  3명이 건너갔다고 가정.  0의 연속된 구간이 K만큼 인지 아닌지 체크하면 m번 째 사람이 건너간 건지 아닌지를 파악할 수 있음.(만약 0이 k만큼 연속되지 않았다면 3번째 사람은 건너간 것.)

 

 - 만약 0이 k만큼 반복됬다면 m번째 사람은 통과하지 못한 것. 반복되지 않았다면 m번째 사람은 통과한 것.

 

 - 위의 결과에 따라 이분 탐색의 범위를 적절히 조절해준 뒤 전체 과정 반복.

 

[코드]

1. 정확성 테스트만 통과

public int solution(int[] stones, int k) {
        int[] step = new int[stones.length+2];            //출발과 도착지점을 따로 둠
        for(int i = 1; i < step.length-1; i++) {        //첫 번째와 마지막 칸을 -1로 초기화
            step[i] = stones[i-1];  
        }
        step[0] = -1;                                    //첫과 끝을 초기화
        step[step.length-1]= -1;
            
        boolean flag = true;                                //m번째 사람이 건널 수 있는지 없는지
        int count = 0;                                        //건넌 사람 수
        
        while(flag) { 
            for(int i = 0; i < step.length-1; i++) {        //징검다리 한명 당 
                if(step[i+1] != 0 && step[i+1] != -1) {        //0이 아니면 1을 빼줌.
                    step[i+1]--;                
                }else {                                        //0일 경우 반복문이 하나 더 필요함.
                    for(int j = i+1; j <= i+1 + k; j++) {
                        if(j == i+1 +k) {                    //j가 k범위를 넘어서 뛰려고 하면 종료
                            flag = false; break;
                        }
                        if(step[j] == -1) {                    //마지막에 도착하면 종료
                             break;
                        }
                        if(step[j] != 0) {                    //건너려고 하는 곳이 0이 아니면 그 부분에서 다시 시작.
                            i = j-1;  step[j]--; break;
                        }
                    } 
                }
            }
            if(flag) count++;
            else break;
        }
        return count;
    }

 

2. 효율성 테스트도 통과

public int solution(int[] stones, int k) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        int mid = 0;
        int count = 0;                        //0이 연속적으로 나오는지 확인
        boolean flag = false;                //r을 줄일지 l을 줄일지 파악(ex.0이 연속으로 나오면 r을 줄여야함)
        int answer = 0;
        while(l <= r) {
            int[] stoneA = stones.clone();  //매번 필요하므로 주소값이 stones을 가르키지 않게 
            mid = (l+r)/2;
            count= 0;
            flag = false;        
            
            for(int i = 0 ; i < stoneA.length;i++) { //0으로 바꿔줬음
                if(stoneA[i] <= mid) {
                    stoneA[i] = 0;
                    count++;
                    if(count == k) {                //0의 개수가 K와 같으면 건너지 못함.
                        flag = true;                //건너지 못하므로 사람 순서를 더 적게해서 도전한다.
                        break;
                    }
                }else {                                //연속되지 않으면 count를 0으로 초기화
                    count =0;
                }
            }
            if(flag) {                                //mid번 째 사람이 넘는지 안넘는지에 따라 r,l조정
                r = mid -1;
                answer = mid;                        //true 즉 건널 수 있을 때 건너간 mid번째 사람을 저장.
            }else {
                l = mid +1;
            }
        }
        return answer;
    }

프로그래머스 테스트 케이스 통과

느낀 점 : 카카오 문제들은 항상 풀면서 위기들이 찾아오는 것 같다. 다행히도 필기를 계속하면서 풀어서 그런지 시간이 오래 걸리는 문제는 없었다. 언제 하루 날 잡고 카카오 문제만 푸는 시간을 가져야겠다.