[프로그래머스] 징검다리 건너기 - JAVA

in Algorithm on 기타

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

풀이

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

위과 같은 배열으로 징검다리들의 숫자가 입력으로 들어온다.

디딤돌을 밟을때마다 숫자가 1씩 줄어들고, 0인 돌이 있다면 안뛰고 건너뛸 수 있다.

하지만, 입력으로 k가 주어지는데 한번에 k개의 돌만 건너뛸 수 있다.

예를 들어, [5, 3, 2, 1, 4] 이러한 배치를 하고있다면

3명이 돌을 건너간 후의 상태는 [2, 0, 0, 0, 1]이 된다.

k가 3일 때, 2인 돌에서 1인 돌로 뛰려면 4칸을 뛰어야하기 때문에 이는 불가능하다.

즉, 건널 수 있는 최대 인원 수는 3명이 된다.

k개씩 구간을 나눠 그 중 최댓값이 그 구간을 건널 수 있는 최대 인원 수가 된다.

일정 구간에서 최댓값을 찾아야하기때문에 세그먼트트리를 적용했다.

k개의 구간을 보면서 그 중 최댓값을 찾고, 그 최댓값들 중 가장 작은 값이 전체 구간에서 건널 수 있는 최대 인원 수가 된다.

세그먼트 트리를 이용해서 풀었지만 다른 풀이들을 찾아보니 이분탐색으로 푼 사람들이 대부분이었다.

메모리: 63.8MB

시간: 43.90ms

언어: Java 11

코드

import java.util.*;

class Solution {
    static class SegmentTree {
        int[] tree;
        int treeSize;

        public SegmentTree(int arrSize) {
            int height = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
            this.treeSize = (int) Math.pow(2, height + 1);
            tree = new int[treeSize];
        }

        public int init(int[] arr, int node, int start, int end) {
            if(start == end) {
                return tree[node] = arr[start - 1];
            } else {
                return tree[node] = Math.max(init(arr, node * 2, start, (start + end) / 2), init(arr, node * 2 + 1, (start + end) / 2 + 1, end));
            }
        }

        public int maxValue(int node, int start, int end, int left, int right) {
            if(left > end || right < start) {
                return 0;
            }

            if(left <= start && end <= right) {
                return tree[node];
            }

            return Math.max(maxValue(node * 2, start, (start + end) / 2, left, right), maxValue(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
        }
    }

    public int solution(int[] stones, int k) {
        int len = stones.length;
        SegmentTree seg = new SegmentTree(len);
        seg.init(stones, 1, 1, len);

        int answer = 200_000_001;
        for(int i = 1; i <= len + 1 - k; i++) {
            answer = Math.min(seg.maxValue(1, 1, len, i, i + k - 1), answer);
        }

        return answer;
    }
}