프로그래머스: 징검다리 건너기⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
체감 난이도 : ⭐⭐⭐
유형 : 이분 탐색, 슬라이딩 윈도우
걸린 시간: 1시간 초과!
🧐 문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오 초등학교의 “니니즈 친구들”이 “라이언” 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. “라이언” 선생님은 “니니즈 친구들”이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
- 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 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
첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.
첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.
두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.
세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.
따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.
✏️ 풀이 과정
이 문제는 최대 몇명이 디딤돌을 건널 수 있는가? 묻는 문제이다.
해당 질문에 대답하기 위해, 아래를 떠올렸다.
- k만큼의 범위에서의 최대 값을 구하면, 해당 범위의 디딤돌을 건널 수 있는 최대 인원 수이다.
- 디딤돌 모든 위치에서 1번을 적용한다.
- 2번에서 구한 값 중, 최소 값을 구하면 문제의 답을 구할 수 있을 것이다.
이 것을 떠올리긴 했는데, 어떤 식으로 최적화 해야할지가 떠오르지 않았다.
1시간 30분 이상 시간을 투자할 수는 없었기에, 다른 사람의 힌트를 살펴보았다.
sliding window와 Deque 자료구조를 이용합니다.
stones 배열을 (index, value) 쌍으로 매핑한 뒤 순회합니다.
1. Deque 에 뒤에서부터 집어 넣습니다.
2. Deque의 마지막 원소가 집어넣을 원소보다 작다면, pop 해줍니다.
3. Deque의 첫번째 원소가 현재 index - k 를 벗어났다면, pop 해줍니다.
이렇게 하면 Deque[0]가 해당 구간의 max 값입니다.
Deque 자료구조는 head 와 tail 의 삽입, 삭제가 모두 O(1) 이기에 max 값을 O(1) 시간에 구할 수 있습니다.
answer 은 여기서 구해진 max 값 중 가장 작은 값이 됩니다.
사실상 거의 답지이다.
이 알고리즘을 sliding window maximum이라고 한다.
✏️ 나의 풀이(첫 시도)
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> stones, int k) {
int totalMin = *max_element(stones.begin(), stones.begin()+k);
int curMax = totalMin;
int last = 0;
for(int i=k; i<stones.size(); i++) {
if(stones[last] == curMax) {
int temp = *max_element(stones.begin()+last+1, stones.begin()+last+1+k);
curMax = temp;
totalMin = min(totalMin, curMax);
}
last++;
}
return totalMin;
}
- 1시간이 넘어갈 때, 일단 급하게 코드를 완성해보자라는 마음으로 만들었다.
- 현재 범위에서의 최대 값을 curMax에 저장해두었다가, 해당 값이 빠져나갈 때 다시 갱신해준다.
- 최적화를 위해, 나름 급하게 시도한 것이다.
- 총 97.4점을 맞았다.
- 정확성 테스트: 모두 통과
- 효율성 테스트: 1개 실패
✏️ 나의 풀이
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> stones, int k) {
int result = INT_MAX;
deque<int> dq;
for(int i=0; i<stones.size(); i++) {
while(!dq.empty() && stones[dq.back()] < stones[i]) dq.pop_back();
dq.push_back(i);
if(dq.front() <= i-k) dq.pop_front();
if(i >= k-1) result = min(result, stones[dq.front()]);
}
return result;
}
- 힌트를 확인하고 짠 코드이다.
- sliding window maximum 알고리즘을 사용하였다.
✔️ 다른 사람의 풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int search(vector<int> stones, int mid, int k){
int cnt = 0;
for(int i = 0; i < stones.size();i++){
if(stones[i] < mid)
cnt++;
else
cnt = 0;
if(cnt >= k) return -1;
}
return 1;
}
int solution(vector<int> stones, int k) {
int answer = 0;
int start = 0;
int end = *max_element(stones.begin(),stones.end());
while(start <= end){
int mid = (start + end) / 2;
if(search(stones,mid,k) == 1){
start = mid + 1;
if(answer < mid)
answer = mid;
}else
end = mid -1;
}
return answer;
}
🧐 분석
- 이분탐색을 사용하고 있다.
- 특정 인원 mid를 가정하고, 돌 내구도에서 mid를 뺐을 때, 연속으로 k번 이상 0 이하가 되는 구간이 있는지 확인한다.
- 있다면 건너지 못한다.
- 없다면 건널 수 있다.
-
위 값을 기준으로, 이분탐색의 범위를 더 좁게 조정한다.
- 와… 이분탐색을 전혀 생각해보지 못했다..
🪶 후기
1시간 제한을 걸고 하면, 3단계는 감은 잡지만, 풀기가 힘들다.
그래서 그런가 요즘 PS 실력이 낮다는게 느껴진다.
시간 제한이 따로 없으면, 무조건 풀긴하는데 이러면 의미가 없으니..
댓글남기기