징검다리 건너기
2019 카카오 개발자 겨울 인턴쉽
https://school.programmers.co.kr/learn/courses/30/lessons/64062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 문제
2. 풀이
2.1 풀이 방법
캐릭터들이 징검다리를 건널 때마다 징검다리의 숫자가 1씩 깎이고 징검다리의 숫자가 0이 되면 캐릭터는 그 징검다리를 뛰어넘을 수 있으며, 캐릭터는 k만큼 건너뛸 수 있다.
만약 숫자가 0인 징검다리가 연속해서 k만큼 이어져있으면 캐릭터는 징검다리를 뛰어 넘을 수 없으므로 징검다리를 건너갈 수 없다.
따라서 이 문제는 캐릭터들이 징검다리를 건넜을 때, 숫자가 0인 징검다리가 연속해서 K개 만큼 나오는 순간을 찾으면 된다.
그리고 숫자가 0인 징검다리가 연속해서 K개 만큼 나오는 순간까지 징검다리를 건넌 캐릭터의 수가 이 문제의 답이 된다.
이는 주어진 징검다리에서 K길이의 모든 구간을 탐색해서 찾을 수 있다.
모든 K길이의 구간에서 징검다리의 숫자가 0이 될 때까지 징검다리를 건널 수 있는 캐릭터의 수를 구하고 그 최솟값을 구하면 된다.
예를 들어, 문제의 예시처럼 징검다리가 주어지고 K = 3이라고 하자.
[징검다리 예시]
이제 K(=3) 구간만큼 탐색을 하면서 해당 구간의 숫자가 모두 0이 될 때까지 건널 수 있는 캐릭터의 수를 구한다.
[K길이의 구간 탐색]
첫 구간인 (2, 4, 5)가 전부 0이 되려면 5명의 캐릭터가 지나가면 된다.
[지나갈 수 있는 캐릭터 수 갱신]
이제 오른쪽으로 이동하며 차례대로 각 구간을 탐색한다.
[구간 이동]
계속 탐색하면서 지나갈 수 있는 캐릭터 수 를 갱신해 준다.
[구간 이동&갱신]
탐색하는 구간에 5가 있었을 때는 5가 최댓값이기 때문에 최소 5명의 캐릭터가 지나가야 모든 징검다리가 0이 되었다.
위 예시의 구간 (3, 2, 1)에서는 3이 최댓값이기 때문에 최소 3명의 캐릭터가 지나가면 모든 징검다리가 0이 된다.
즉, 이 징검다리에서는 캐릭터가 3명만 지나가도 징검다리의 숫자가 3개만큼 연속해서 0이 되는 구간이 있다는 것이고 이는 해당 징검다리는 최대 3명까지의 캐릭터만 건널 수 있다는 것을 의미한다.
이런 식으로 각 구간에서 지나갈 수 있는 캐릭터의 수를 구하고 그중 최솟값을 구하면 최종적으로 징검다리를 건널 수 있는 캐릭터의 수를 구할 수 있다.
2.1.1 window slide maximam
이 문제는 다음과 같은 절차로 풀 수 있다.
1. 모든 k길이의 구간을 탐색
2. k길이의 구간에서 최댓값(캐릭터가 징검다리를 건널 수 있는 수)을 찾는다.
3. 각 구간의 최댓값의 최솟값이 답이 된다.
문제는 2번의 k길이의 구간에서 최댓값을 찾는 것이다.
k길이의 구간에서 최대값을 찾을 때 단순하게 구간의 모든 원소를 확인하는 방법을 쓴다면 시간복잡도는 다음과 같다.
O(N*K)
징검다리와 k의 최댓값이 200,000이므로 시간복잡도가 10억을 훨씬 넘어가기 때문에 해당 방식은 시간 초과가 나게 된다.
때문에 시간복잡도를 해결할 각 구간의 최댓값을 구하는 방법을 찾아야 할 필요가 있다.
다행히도 특정 구간을 이동시키면서 구간의 최대값을 구하는 방법이 있다.
방법은 다음과 같다.
우선 자료구조로 DeQue를 사용한다.
DeQue에는 인덱스가 들어가며, 우리는 DeQue의 가장 앞에 있는 인덱스의 값을 구간의 최댓값이 되게 할 것이다.
이를 위한 순서는 다음과 같다.
1. 만약 DeQueue의 가장 앞에있는 값이 구간을 벗어났다면 앞에있는 값을 빼준다.
2. 새롭게 추가되는 원소는 DeQueue의 뒤에 넣는다.
3. 새롭게 추가되는 원소가 DeQueue의 마지막값보다 크다면 마지막 값을 DeQueue에서 뺀다.
4. 3을 반복한다.
우리는 구간을 오른쪽으로 이동시킬 것이기 때문에 새롭게 추가된 원소보다 왼쪽에 있는 값들 중 더 작은 값들은 앞으로 절대 해당 구간에서 최대값이 될 수 없다.
따라서 새롭게 추가되는 원소보다 값이 작은 값들은 전부 DeQueue에서 빼주는 것이다.
이 방법을 앞의 예시와 같이 확인해 보자.
[Deque 사용 예시 그 1]
이제 앞에서 설명한 절차대로 DeQueue를 채우며 각 구간의 최댓값을 구하고 지나갈 수 있는 캐릭터 수를 갱신한다.
기본적으로 각 원소를 하나씩 순회하며 구간을 탐색한다.
[Deque 사용 예시 그 2]
초기에는 구간의 길이가 k가 될 때까지 지나갈 수 있는 캐릭터의 수는 갱신하지 않는다.
또한 위의 예시에서는 편의상 DeQueue에 징검다리의 값이 들어가 있지만 실제 코드에서는 징검다리의 인덱스가 들어가게 된다.
[Deque 사용 예시 그 3]
2보다 새롭게 추가된 4가 더 크기 때문에 2를 DeQueue에서 빼주고 4를 넣는다.
[Deque 사용 예시 그 4]
이번에도 새롭게 추가된 값 5가 4보다 크기 때문에 4를 빼준뒤 5를 넣어준다.
또한 구간의 길이가 k(=3)가 되었으니 이제 구간의 최댓값으로 지나갈 수 있는 캐릭터 수를 갱신해 준다.
이제 계속해서 징검다리의 원소를 하나씩 순회하며 구간을 탐색하고 위 과정을 반복한다.
[Deque 사용 예시 그 5]
[Deque 사용 예시 그 6]
[Deque 사용 예시 그 7]
DeQueue의 가장 앞에 있던 5가 구간에서 벗어났으니 5를 빼준다.
또한 DeQueue의 가장 앞에 있는 값이 이전에 지나갈 수 있는 캐릭터수(=5) 보다 작으니 이에 따라 지나갈 수 있는 캐릭터 수를 갱신해 준다.
이를 반복한다.
[Deque 사용 예시 그 8]
DeQueue에서 가장 앞의 값인 3이 구간에서 벗어났으니 DeQueue에서 제외해 준다.
또한 2, 1 보다 새로 추가될 4가 더 크기 때문에 2, 1을 DeQueue에서 빼주고 4를 추가해 준다.
현재 지나갈 수 있는 캐릭터 수(=3) 보다 현재 구간의 최댓값(=4)이 크기 때문에 지나갈 수 있는 캐릭터 수는 갱신하지 않는다.
[Deque 사용 예시 그 9]
[Deque 사용 예시 그 10]
[Deque 사용 예시 그 11]
3명이 건너면 0이 연속해서 3개 이어진 구간이 있었기 때문에, 최종적으로 이 징검다리에서 지나갈 수 있는 캐릭터 수는 3명이 최대이다.
2.2 코드
[solution]
public int solution(int[] stones, int k) {
Deque<Integer> deque = new LinkedList<>();
//result = 징검다리를 지나갈 수 있는 캐릭터 수
int result = Integer.MAX_VALUE;
for (int i = 0; i < stones.length; i++) {
//Deque가 비어있는 경우(i = 0 일 때)에는 인덱스를 Deque에 우선적으로 넣어준다.
if (deque.isEmpty()) {
deque.offer(i);
}
Integer frontIndex = deque.peek();
//Deque의 가장 앞의 값이 구간을 벗어났다면 Deque에서 제외해준다.
if (i - frontIndex >= k) {
deque.poll();
}
//Deque의 마지막 값이 새롭게 추가될 값보다 작다면 Deque에서 빼준다.
while (!deque.isEmpty()) {
if (stones[deque.peekLast()] <= stones[i]) {
deque.pollLast();
} else {
break;
}
}
deque.offer(i);
//현재 구간의 최대값을 기준으로 result(징검다리를 건널 수 있는 캐릭터 수)를 갱신해준다.
if (i >= k - 1) {
result = Math.min(result, stones[deque.peek()]);
}
}
return result;
}
3. 전체 코드
[전체 코드]
import java.util.Deque;
import java.util.LinkedList;
public class 징검다리_건너기 {
public int solution(int[] stones, int k) {
Deque<Integer> deque = new LinkedList<>();
//result = 징검다리를 지나갈 수 있는 캐릭터 수
int result = Integer.MAX_VALUE;
for (int i = 0; i < stones.length; i++) {
//Deque가 비어있는 경우(i = 0 일 때)에는 인덱스를 Deque에 우선적으로 넣어준다.
if (deque.isEmpty()) {
deque.offer(i);
}
Integer frontIndex = deque.peek();
//Deque의 가장 앞의 값이 구간을 벗어났다면 Deque에서 제외해준다.
if (i - frontIndex >= k) {
deque.poll();
}
//Deque의 마지막 값이 새롭게 추가될 값보다 작다면 Deque에서 빼준다.
while (!deque.isEmpty()) {
if (stones[deque.peekLast()] <= stones[i]) {
deque.pollLast();
} else {
break;
}
}
deque.offer(i);
//현재 구간의 최대값을 기준으로 result(징검다리를 건널 수 있는 캐릭터 수)를 갱신해준다.
if (i >= k - 1) {
result = Math.min(result, stones[deque.peek()]);
}
}
return result;
}
}
댓글