2019 카카오 개발자 겨울 인턴십 코딩테스트 - 징검다리 건너기(feat. Java)

문제 정보는 아래 링크를 확인해주세요!

 

[징검다리 건너기]

프로그래머스

문제 접근방법

- 나니즈 친구들이 최대로 징검다리를 건널 수 있는 경우는

  처음 징검다리부터 k개의 연속된 징검다리 집합 {1~k}

  두번째 징검다리부터 k개의 연속된 징검다리 집합 {2~k}

  n-k번째 징검다리부터 k개의 연속된 징검다리 집합 {n-k~k}가 있고,

 

- 이 집합 안에서 최댓값을 구해주고,

  집합의 최댓값과 다른 집합의 최댓값을 비교해서 최솟값을 구해주는 것이 문제 접근 방법이다.

 

- k개의 징검다리를 건널 수 있기 때문에 건널 수 있는 징검다리 수로 집합을 만들어 준 것이고

- k개만큼 건널 수 있기 때문에 그 집합 안에서의 최댓값이 나니즈 친구들이 최대로 건널 수 있는 갯수이다.

- 그리고 이 집합의 최댓값 중에 최솟값이 가장 먼저 징검다리 k개가 없어지는 곳이므로

  이 최솟값이 결과값이라고 할 수 있다.

 

[소스코드]

package algorithm.programmers;

/*
* 2019 카카오 개발자 겨울 인턴십
* 징검다리 건너기
* */
public class Pro64062 {

    public int solution(int[] stones, int k) {

        int min = Integer.MAX_VALUE;//구간의 max 값 중에 최솟값

        for (int i = 0; i <= stones.length-k;) {//징검다리 갯수-k만큼 분기문을 돌려준다.
            //System.out.println(i);

            int max = stones[i];//구간의 처음 요소를 max 변수에 추가

            int idx = 0;//다음 i의 위치를 지정할 인덱스 변수

            for (int j = i+1; j < i+k; j++) {//k만큼의 구간 탐색

                if (stones[j] >= max) {//현재 구간의 징검다리가 구간의 최댓값보다 크거나 같을 때

                    idx = j;//인덱스를 현재 징검다리 번호로 변경
                    max = stones[j];//구간의 최댓값을 현재 징검다리로 변경
                }
            }

            if (idx == 0) i++;//구간의 최댓값이 변경되지 않았을 때는 한칸만 이동
            else {//구간의 최댓값이 변경되었을 때는 최댓값에 해당하는 징검다리 번호+1로 이동
                i = (idx+1);
            }

            min = Math.min(min,max);//구간의 최댓값이 다른 구간과 비교했을 때, 더 작은 구간의 최댓값을 결값에 설정
        }

        return min;
    }
}

 

[정확성 테스트]

[효율성 테스트]

 

 

이렇게  2019 카카오 개발자 겨울 인턴십 코딩테스트를 모두 풀어보았다!

 

효율성테스트 때문에 시간이 오래걸린감이 있기는한데 난이도는 프로그래머스 레벨 3정도 수준인 것 같다.