Algorithm/문제풀이
2022. 12. 23. 19:23
문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
트럭 여러 대가 다리를 지나는데
트럭들은 길이가 1이라고 생각하고
다리의 길이는 bridge_length, 무게 제한은 weight인 조건에서
모두 지나가는데 걸리는 시간을 계산하는 문제이다.
나의 풀이 전략
1. while 문으로 시간을 계산한다.
2. 다리 위에 있는 트럭들을 큐(onBridge)로 구현한다.
3. 큐의 맨 앞 쪽 차량을 내보내면서 다음 차량이 들어올 수 있다면 다리 위에 올린다.
상세
0. answer 보단 time이 더 직관적이다.
truck_weights보단 Deque 형식의 waitings가 더 직관적이다.
그리고 다리 위의 트럭들을 구현하기 위해 onBridge라는 객체를 선언해주자.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
int time = 0;
deque<int> waitings(truck_weights.begin(), truck_weights.end());
deque<int> onBridge;
return time;
}
(Deque가 기능도 많고 여러 함수들과도 잘 어울린다. 적극적으로 이용해야겠다.)
1. 우선 모든 트럭들은 다리를 지나갈 수 있다는 것을 알자. (제한 조건 참고)
따라서 while 문으로 대기 차량들이 다 빠져나갈 수 있을 때까지 시간을 재본다.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
// ...
while(waitings.size())
{
time++;
}
return time;
}
2. 다음 차량이 들어올 수 있으려면
우선 다리가 꽉 차 있으면 안 된다.
다리가 꽉 차면 맨 앞 차량을 빼주자.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
// ...
while(waitings.size())
{
// ...
if(onBridge.size() == bridge_length)
onBridge.pop_front();
}
return time;
}
3. 다음으로 볼 것은 무게이다.
다리 위의 모든 차량의 무게(sumWeight)와 다음 차량의 무게(nextWeight)까지 합한 것이
다리의 무게제한(weight) 이하라면
다리 위에 차량을 올려주자.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
// ...
while(waitings.size())
{
// ...
int sumWeight = accumulate(onBridge.begin(), onBridge.end(), 0);
int nextWeight = waitings.front();
if(sumWeight + nextWeight <= weight)
{
onBridge.push_back(waitings.front());
waitings.pop_front();
}
}
return time;
}
4. 만약 다음 차량을 무게제한 때문에 올리지 못한다면 어떻게 해야 하는가?
이대로 둔다면 while 문은 무한루프에 빠지게 될 것이다.
이를 방지하기 위해서는
무게가 0인 차량이 올라갔다고 생각하는 것이다.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
// ...
while(waitings.size())
{
// ...
if(sumWeight + nextWeight <= weight)
{
onBridge.push_back(waitings.front());
waitings.pop_front();
}
else onBridge.push_back(0);
}
return time;
}
5. 이렇게 하면 waitings는 다 비워졌다.
하지만 onBridge에 차량이 남아있다.
waitings가 다 비워진 시점은
waitings의 마지막 차량이 다리 위에 올라간 시점이다.
따라서 마지막 차량까지 건너는 시간(bridge_length)을 더해서 반환해줘야 한다.
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
while(waitings.size())
{
// ...
}
return time + bridge_length; // 주의!
}
전체 소스코드
#include <vector>
#include <queue>
#include <numeric> // accumulate
#include <iostream>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
int time = 0;
deque<int> waitings(truck_weights.begin(), truck_weights.end());
deque<int> onBridge;
while(waitings.size())
{
time++;
if(onBridge.size() == bridge_length)
onBridge.pop_front();
int sumWeight = accumulate(onBridge.begin(), onBridge.end(), 0);
int nextWeight = waitings.front();
if(sumWeight + nextWeight <= weight)
{
onBridge.push_back(waitings.front());
waitings.pop_front();
}
else onBridge.push_back(0);
}
return time + bridge_length;
}
int main()
{
solution(2, 10, {7,4,5,6});
return 0;
}
'Algorithm > 문제풀이' 카테고리의 다른 글
[프로그래머스] JadenCase 문자열 만들기 | C++ (0) | 2022.12.26 |
---|---|
[프로그래머스] 다음 큰 숫자 | C++ (0) | 2022.12.26 |
[프로그래머스] 숫자의 표현 | C++ (0) | 2022.12.23 |
[프로그래머스] 크레인 인형 뽑기 | C++ (2) | 2022.12.22 |
[백준] 3987 | 보이저 1호 | C++ (0) | 2022.10.14 |