스택은 진짜 그냥 맨날 나오는 문제 유형이다. 면접에서도 중요한 개념으로서 이용하라고 문제 냈는데 틀렸다....
탑
사실전에 백준에서 풀어본 문제다. 그럼에도 풀이가 기억나지는 않음 스택을 쓴다는 것 정도 ㅋㅋ. 코딩테스트에서도 실제로 만났던 문제인데 그 당시에는 풀 줄 몰랐다.
| [6,9,5,7,4] | [0,0,2,2,4] |
예제를 분석해보면 6은 맨 왼쪽이라 0 , 9는 왼쪽에 자기보다 큰게 없어서 0, 5는 왼쪽에 9가 있으니 2, 7도 왼쪽에 5는 스킵되고 9가 있으니 2, 4는 7이 바로 왼쪽에 있으니 4이다.
그럼 목표는 모든 위치에서 왼쪽에 가장 먼저 자기보다 큰 기둥을 찾는 것이다.
스택에 넣다가 해당 위치에서의 답을 구하려면 스택에서 빼면서 먼저 만나는 자기 보다 큰 값을 확인하면 될거 같은데 이러면 뺀 놈을 나중에 다시 확인할 수 가 없다. -> 그러니까 중간에 스택 팝을 시작하기 보다 전부 넣고 하면 될거 같다.
다시 예시를 보면 그럼 4는 쉽게 구하고 7은 5를 팝하고 9에서 값이 정해진다. 그러면 5는 어떻게 해야 하는가 하면 7이 9를 찾는 과정에서 5는 7이 9를 찾으면 자동으로 9의 위치가 답이된다. 즉 이때는 5에 대해서 일일이 해줄 필요없이 9의 위치가 되는 답이 2개라는 것을 자동으로 알 수 있다. 그럼 9도 마찬가지로 스택이 empty가 되었을때 6까지 답이 0이 된다.
이걸 스택으로 구현하니까 일일이 저장할 갯수, index를 다 저장해야되서 복잡해 졌다. 그냥 벡터로 구현할 수 있을거 같은데?
#include <string>
#include <vector>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> st;
vector<int> solution(vector<int> heights) {
vector<int> answer;
for (int i = 0; i < heights.size(); i++) {
st.push(heights[i]);
}
int cur;
int ind = st.size();
int cnt = 1;
while (!st.empty()) {
if (!st.empty()) {
cur = st.top();
st.pop();
ind--;
}
while(!st.empty()) {
if (st.top() > cur) {
for (int i = 0; i < cnt; i++) {
answer.push_back(ind);
}
cnt = 1;
break;
}
else {
cnt++;
st.pop();
ind--;
}
if (st.empty())
{
for (int i = 0; i < cnt; i++) {
answer.push_back(0);
}
}
}
}
reverse(answer.begin(), answer.end());
return answer;
}
void main() {
vector<int> ht;
ht.push_back(6);
ht.push_back(9);
ht.push_back(5);
ht.push_back(7);
ht.push_back(4);
solution(ht);
}| [1,5,3,6,7,6,5] | [0,0,2,0,0,5,6] |
아 근데 이 알고리즘은 이 경우에 안된다. 실행한 결괏값 { 0, 0, 0, 0, 0, 5, 6 }이(가) 기댓값 { 0, 0, 2, 0, 0, 5, 6 }와(과) 다릅니다.
왜 맨날 나는 못푸는 걸까.... 풀이에 심각한 허점이 있음....
어쨋든 이걸 해결하려면 위처럼 중간에 값들을 무시하는 행보는 안된다. 3처럼 가운데 있는데 답이 0이 아니라 2일 수도 있다. 무시하지 말고 왼쪽으로 보면서 확인해보고 답이 없으면 0이지 있을 수 도 있다고 봐야 한다. 음 6,7이 0임을 알려면 3이 2임이 구해진 다음에 알 수 있는거 아닌가? -> 각 값의 정답을 배열에 저장하면 되지 않을까? 순서대로 answer에 푸쉬할 필요 없이 그냥 구해지는 답별로 넣으면 될거 같은데.
도저히 모르겠어서 스택의 기능에 대해서 생각해보자. 스택은 푸쉬후 팝을 하면서 오른쪽에서 왼쪽으로 순차적으로 바로 왼쪽 값을 확인할 수 있다. 음 배열이랑 비교해보면 스택은 그냥 동작 원리 그 자체 같은데, 왼쪽으로 확인한다는 사실.
음 문제가 각 위치 즉 st.top()에서 바로 왼쪽에 값이 없으면 아직 못찾은것을 기억했다가 왼쪽에서 찾아야하는데. 즉 6,7은 답을 못찾고 3이 먼저 답을 찾도록 해야 한다. 이걸 문제로 다시 말하면 6,7을 스킵하고 3이 먼저 답을 찾고 그후에 6,7의 답을 찾도록 해야한다. 스택의 맨위에서 부터 보면서 현재 값 보다 작은 값이 top이면 그 top의 답이 왼쪽에서 발견될 수도 있으니 작은 값이 주인공이 되는거 같다. -> 아 힌트를 얻었다. 스택에 발견하지 못한 값들을 넣어 준다. 그리고 작은 값에 대해 발견된 경우 큰 값도 발견될 수 있는지 스택에서 팝하면서 확인하면 된다.
아 근데 구현을 실패 했다.
#include <string>
#include <vector>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> st;
vector<int> solution(vector<int> heights) {
vector<int> answer;
//answer.push_back(0);
for (int i = 0; i < heights.size(); i++) {
st.push(heights[i]);
}
for (int i = heights.size() - 1; i >= 0; i--) {
while(!st.empty() && heights[i] > st.top()) {
answer.push_back(i+1);
st.pop();
}
}
while (!st.empty()) {
answer.push_back(0);
st.pop();
}
reverse(answer.begin(), answer.end());
return answer;
}
void main() {
vector<int> ht;
ht.push_back(6);
ht.push_back(9);
ht.push_back(5);
ht.push_back(7);
ht.push_back(4);
solution(ht);
}답을 못구한 타워는 스택에 넣고(왼쪽이 top이 되도록) 나중에 왼쪽에서 확인해 본다고 했는데, 그 확인하는 과정을 어떻게 해야할지 모르겠다....
아 음 너무 어렵게 생각한거 같다. 히스토그램 백준 문제처럼 자꾸 스택 비슷한게 나오면 어렵게 생각하는거 같다.
그냥 이거였다. 사이즈가100으로 작아서 가능한건가? 10만이였으면 어땠을까.......
#include <string>
#include <vector>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> st;
vector<int> solution(vector<int> heights) {
vector<int> answer;
for (int i = 0; i < heights.size(); i++) {
for (int j = i; j >= 0; j--) {
if (heights[j] > heights[i]) {
answer.push_back(j+1);
break;
}
else if (j == 0) {
answer.push_back(0);
}
}
}
return answer;
}
void main() {
vector<int> ht;
ht.push_back(6);
ht.push_back(9);
ht.push_back(5);
ht.push_back(7);
ht.push_back(4);
solution(ht);
}
문제를 찾아보자. (링크 첨부 예정)
1. 10만인 경우
2. 히스토그램이랑 비교
3. 물이 고이는 넓이 구하는 문제
다리를 지나는 트럭
다리 길이가 있고, 다리가 버틸 수 있는 총 무게가 있다,트럭이 다리를 1초에 1씩 지나갈때 얼마나 걸리는지 구하라는거.
경과 시간 다리를 지난 트럭 다리를 건너는 트럭대기 트럭
| 0 | [] | [] | [7,4,5,6] |
| 1~2 | [] | [7] | [4,5,6] |
| 3 | [7] | [4] | [5,6] |
| 4 | [7] | [4,5] | [6] |
| 5 | [7,4] | [5] | [6] |
| 6~7 | [7,4,5] | [6] | [] |
| 8 | [7,4,5,6] | [] | [] |
문제에서 주어진 이 표를 보니까 조금은 구상되는거 같다. 어차피 모두 지나가야 되니까 다리 무게가 버틸 수 있을때 까지 매초 무거운 트럭부터 보내고, 다리를 건너는 트럭들은 배열에 저장해 놓고 경과 시간이 다리 길이만큼 지나면 배열에서 제거한다. 이런 방식으로 모든 트럭이 지나가면 종료하고 경과 시간을 구한다.
근데 여기서 경과 시간 1~2 사이 같은 경우는 다리로 트럭이 올라올 수 없는 때니까 시간 경과를 일초씩 반복문을 돌리기 보다. 다리 건널때 까지 남은 시간 그냥 바로 더 해버려도 될거 같다.
아 근데 구현하니까 틀렸다. 변수도 몇개 생기고 그러니까 내가 생각한 알고리즘 대로 구현을 못했다.
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
vector<int> onBridge;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
sort(truck_weights.begin(), truck_weights.end(), greater<int>());
int next_truck_ind = 0;
int time_elapsed = 0;
int weightSum = 0;
int front = 0;
onBridge.push_back(time_elapsed);
weightSum += truck_weights[0];
while (1) {
if (onBridge.size() <= front) {
break;
}
else {
}
//다리에서 내려야할 트럭이 있는가.
if ( time_elapsed - onBridge[front] >= bridge_length) {
front++;
}
//현재 다리에 트럭이 추가로 올라 올 수 있는가.
if (weight > truck_weights[next_truck_ind] + weightSum) {
onBridge.push_back(time_elapsed);
weightSum += truck_weights[next_truck_ind];
next_truck_ind++;
time_elapsed++;
}
else {
//시간을 워프해서 맨 앞 트럭을 다리에서 내린다.
time_elapsed += ( bridge_length + time_elapsed - onBridge[front]);
//트럭 한대를 다리에 놓는다.
time_elapsed++;
onBridge.push_back(time_elapsed);
front++;
}
}
answer = time_elapsed;
return answer;
}
void main() {
int bridge_length = 2;
int weight = 10;
vector<int> truck_weights;
truck_weights.push_back(7);
truck_weights.push_back(4);
truck_weights.push_back(5);
truck_weights.push_back(6);
cout << solution(bridge_length, weight, truck_weights) << "\n";
}음 다시 정리해도 틀렸다. 내일 깔금하게 설계해보자. 내가 설계에 약한듯. 재귀 문제도 이런식으로 나온거 틀렸었다.
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
vector<int> onBridge;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
sort(truck_weights.begin(), truck_weights.end(), greater<int>());
int next_truck_ind = 0;
int time_elapsed = 1;
int weightSum = 0;
int front = 0;
onBridge.push_back(time_elapsed);
weightSum += truck_weights[next_truck_ind];
next_truck_ind++;
while (1) {
if (onBridge.size() <= front) {
//why?
// time_elapsed++;
break;
}
//다리에서 내려야할 트럭이 있는가.
if ( time_elapsed - onBridge[front] >= bridge_length) {
weightSum -= truck_weights[front];
front++;
}
//현재 다리에 트럭이 추가로 올라 올 수 있는가.
if (next_truck_ind < truck_weights.size() && weight >= truck_weights[next_truck_ind] + weightSum) {
onBridge.push_back(time_elapsed);
weightSum += truck_weights[next_truck_ind];
next_truck_ind++;
time_elapsed++;
}
else if(front < truck_weights.size() ) {
//시간을 워프한다.
int inc = (bridge_length - (time_elapsed - onBridge[front]));
time_elapsed += inc;
if (inc == 0) {
time_elapsed++;
}
}
}
answer = time_elapsed;
return answer;
}
void main() {
int bridge_length = 100;
int weight = 100;
vector<int> truck_weights;
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
truck_weights.push_back(10);
cout << solution(bridge_length, weight, truck_weights) << "\n";
}다리를 지나는 트럭 - 설계? 수도 코드...?
while(1){
//다 건넜으면 끝낸다.
//시간이 경과한다.
//이때 다리가 꽉찼으면 타임 워프하고, 아니면 1초만 지나가면 될듯?
//내릴 수 있는 트럭은 내린다.
//올라 올 수 있는 트럭은 다리로 올라온다.
}
음 위처럼 구현했는데 예제는 맞는데 틀림ㅋㅋ
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
vector<int> onBridge;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
sort(truck_weights.begin(), truck_weights.end(), greater<int>());
int next_truck_ind = 0;
int time_elapsed = 1;
int weightSum = 0;
int front = 0;
onBridge.push_back(time_elapsed);
weightSum += truck_weights[next_truck_ind];
next_truck_ind++;
while (1) {
//종료 조건.
if (onBridge.size() <= front) {
break;
}
//시간을 경과시킨다.
//못태우거나 태울게 없는 경우.
if (next_truck_ind < truck_weights.size() && weight < truck_weights[next_truck_ind] + weightSum) {
//시간을 워프한다.
int inc = (bridge_length - (time_elapsed - onBridge[front]));
time_elapsed += inc;
}
else {
time_elapsed++;
}
//다리에서 내려야할 트럭이 있는가.
if ( time_elapsed - onBridge[front] >= bridge_length) {
weightSum -= truck_weights[front];
front++;
}
//현재 다리에 트럭이 추가로 올라 올 수 있는가.
if (next_truck_ind < truck_weights.size() && weight >= truck_weights[next_truck_ind] + weightSum) {
onBridge.push_back(time_elapsed);
weightSum += truck_weights[next_truck_ind];
next_truck_ind++;
}
}
answer = time_elapsed;
return answer;
}
왜 틀린지 모르겠다. 보류 ㅋㅋ..... -> 아 트럭은 순서대로 지나간다... 정렬하면 안되..... sort()를 빼주니 맞았다. 문제를 대충 읽고 구성하는 경향이 강한거 같다. 문제의 조건들을 제대로 캐치하지 않고 문제를 해결하려하니 자꾸 구멍이 생기는듯..!
다른 분들 풀이를 보니 스택 카테고리임에도 스택으로 푼사람은 아무도 없다. 내가 봐도 그냥 큐 같음 ..... 그리고 나처럼 시간 워프하는 분은 없고 그냥 일초씩 무난하게 푸신 분이 많다.
기능 개발
맨 앞 프로그램을 배포 할 수 있는지 확인한다. 배포 가능하면 그 뒤에 progresses에서 100프로 넘는 모든 프로그램을 배포 하고 벡터에서 제거해 준다(또는 비활성화만, 링크드 리스트로 구현하면 삭제가 쉬울거 같다).
-> 제거하자니 정말 비효율적인거 같아서 방법을 모르겠다. vec.erase()로 지우겠다. 대신 반복문이 끝나고 지워야한다.
당일의 배포 갯수를 answer에 푸쉬 한다.
progresses 안에 있는 것들을 speeds로 매일 더해 준다.
날이 지난다. 다시 처음부터 반복한다.
한번 틀렸었다. 이유는 아래 조건을 잘 못 해석했다.......
● 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses -> 앞에 있는 모든 우선순위가 높은것들이 먼저 되야 뒤에 것들도 수행될 수 있다.
-> (이걸 이렇게 해석하면 아래 처럼 풀 수 있는 걸까?..... ) 맨 앞이 배포되고나서 뒤에 것이 앞에 것과 함께 배포 될 수 있는지 보고 아니면 그냥 배포한다....?
다른 사람 풀이를 보니, 위 조건을 이 제대로 이용해서 푼 사람이 있었다. 반복문은 한개만 사용한다. 맨 앞이 나가는데 필요한 날수를 먼저 세고 maxday를 갱신한다, 뒤에 것들이 maxday보다 작으면 answer에 1을 크면 answer.back()에 1을 더한다.
어떻게 하면 위처럼 생각할 수 있을지 고민해 보았다.
주어진 조건에 진척 정도(목표치)와 , 속도가 있다. -> 여기서 걸리는 일 수를 생각할 수 있을듯.
그리고 우리가 알고자 하는 것은 맨 앞에 것이 나갈때 뒤에 것도 나갈 수 있는지 확인하는 것이다.
-> 나갈 수 있는 지는 완성되는데 걸리는 진척 일 수를 생각해보면 된다. 난 여기서 이 일수를 구하는 방법을 반복문을 돌려서 구할 생각을 했는데, 이분은 나눗셈으로 하신것.....
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |
|---|---|
| 프로그래머스 - 카카오 2020 블라인드 테스트 (블록 이동하기, 문자열 압축) (0) | 2020.01.02 |
| 프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격 (0) | 2019.12.30 |
| 프로그래머스 - 카카오 2020 블라인드 테스트 (자물쇠와 열쇠, 가사 검색) (0) | 2019.12.27 |
| 프로그래머스 - 해쉬 (0) | 2019.12.26 |