LV3 [KAKAO] 징검다리 건너기

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=java 

프로그래머스

 

풀이

 

핵심은, 다리의 일정 K구간이 0이 되면 더 이상 친구들이 다리를 건너지 못한다는 것이다.

 

문제의 예시를 보자.

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

K는 3이고 총 3개의 연속된 발판이 0이 되면 더이상 건너지 못한다.

한칸씩 전진하면서 K씩 나눠서 징검다리를 보면,

 

[2, 4, 5]

[4, 5, 3]

[5, 3, 2]

[3, 2, 1]

[2, 1, 4]

[1, 4, 2]

[4, 2, 5]

[2, 5, 1]

 

로 나눌 수 있다. 그리고 특정 구간이 모두 0이 되기전까지는 다리를 건널 수 있기에 각각의 구간에서 최댓값을 구해준다. 

최댓값들을 모아보면 [5, 5, 5, 3, 4, 4, 5, 5] 가 나온다. 여기서 최솟값이 친구들이 건널 수 있는 횟수이다. (0이 되는순간 못건너기 때문에)

 

따라서, 1 ~ K 구간, 2 ~ K+1 구간 .... 식으로 구간을 나누고, 최댓값을 구하고, 최댓값중 최솟값을 취하면 답을 얻을 수 있다.

 

문제는 시간이다!

 

배열 최대길이는 20만이다. 만약 배열이 20만이고, k가 10만이라면 10만개의 배열을 순회하면서 10만개의 요소들을 검사하면서 최댓값을 찾아야한다. 최댓값을 찾기위해 정렬을 사용한다 하더라도 시간초과가 난다.

 

처음에는 map과 배열을 사용하다가, 이마저도 시간초과에서 못벗어나서 map과 priorityQueue를 혼합했다.

 

map의 역할은 다음과 같다.

• map[Index] = Value
• stones의 인덱스를 키로, 값을 Value로 취한다.
• map에는 내가 원하는 구간의 인덱스 값들만 들어있다.
• 위의 예시로, 만약 내가 지금 취할려는 구간이 [2, 4, 5] 라면 
  map[0] = 2 , map[1] = 4, map[2] = 5 와 같이 저장되어 있다.

priorityQueue는 다음과 같다.

• Node라는 클래스를 요소로 갖는다. (Node는 내가 그냥 임시로 지은 이름이다.)
  (Node는 값인 val, 인덱스인 idx 라는 속성을 갖는다.)
• Node의 val 속성이 가장 큰 Node가 우선순위가 높은 힙이다. (가장 큰 값이 위로 온다.)
• 만약 값을 꺼내서 idx속성을 map에서 검사해봤는데 map에 없다면 해당 값은 우리가 원하는 구간에 존재하지 않는다는 것이다.

 

로직을 보면 우선 초기범위를 설정해서 map과 pq(priorityQueue)에 넣어준다. (이때 포인터 두개를 설정해서 앞과 끝을 설정했다.)

최댓값이 위로 오도록 설정했기에 pq값을 확인하고, 답을 갱신해준다. 

 

이후에는 while문을 돌면서 포인터가 범위에 벗어나기 전까지 반복한다. 

 

각각의 포인터는 한칸씩 전진한다. 각 포인터가 가리키는 인덱스가 기존에는 0, 3 이었다면 1, 4로 변경된다.

여기서 map을 생각해보면 0은 더이상 우리가 취하는 구간이 아니고, 4는 새롭게 들어오는 구간이다.

따라서 0은 map에서 삭제해주고, 4는 추가해준다.

 

그다음에 pq값을 확인해서 가장 큰 값을 가져온다.

단 pq에서 꺼낸다음 바로 사용하는게 아니라, 해당 값의 idx속성을 확인해서 map에 있는지 체크해야한다.

만약 map에 없다면 우리가 취하는 구간에 존재하는 값이 아니기에 pq에서 삭제해주고, map에 존재하는 idx 값이 나올때까지 반복해주면 된다. 

 

 

* 단 조심해야하는건, pq에서 값을 가져올때 peek이나 element와 같이 값만 가져오는 함수를 사용해야한다. 없애는건 map에 없을때만 해당되는 행동이다

 

 

코드

import java.util.*;

class Solution {
    public class Node implements Comparable<Node>{
        public int val;
        public int idx;

        public Node(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }

        @Override
        public int compareTo(Node target) {
            return this.val <= target.val ? 1 : - 1;
        }
    }

    public int solution(int[] stones, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();

        int fptr = 0;
        int rptr = k-1;

        for(int i=fptr; i<=rptr; i++){
            map.put(i, stones[i]);
            priorityQueue.add(new Node(stones[i], i));
        }
        int answer = priorityQueue.peek().val;
        fptr++;
        rptr++;

        while (rptr < stones.length) {
            map.remove(fptr - 1);
            map.put(rptr, stones[rptr]);
            priorityQueue.add(new Node(stones[rptr], rptr));

            fptr++;
            rptr++;

            while (true) {
                if (map.containsKey(priorityQueue.peek().idx)) {
                    if(answer > priorityQueue.peek().val) answer = priorityQueue.peek().val;
                    break;
                }
                priorityQueue.poll();
            }
        }
        return answer;
    }
}

 

후기

 

이 문제도 2시간 넘게 걸린거 같다. 정확성에 대한 아이디어는 금방 캐치할 수 있었는데 pq까지 도달하는데가 한참 걸렸다. 풀고보니 뿌듯하나, 확실히 카카오 레벨3정도 되니까 아이디어가 좋아야한다는 느낌이다.

 

그리고 java로 풀다보니 class선언에다 비교함수까지 선언해야했다. 쉽지않다!