둘 다 골드 5
입력 데이터의 수가 많기 때문에 스택을 이용해서 효율적으로 풀어야 하는 문제들이다.
조금 다르긴 한데 두 문제 다 결은 비슷해서... 하나 풀면 다른 하나도 풀 만 하다.
탑
나보다 왼쪽에 있는 탑 중에서 가장 가까운 나보다 높은 탑의 인덱스를 구하는 문제이다.
왼쪽의 탑 중 가장 가까운 탑을 선택하기 때문에, 탐색은 오른쪽에서 왼쪽 순서로 진행한다.
먼저 맨 오른쪽 탑 인덱스를 넣어준다. 그리고 왼쪽으로 한 칸씩 이동하면서 스택에 인덱스를 넣어줄 건데, 이 때 한 번 검사를 해주어야 한다.
바로 들어오는 인덱스의 탑의 높이가 현재 스택 탑의 탑 높이(ㅋ) 보다 높은지 확인하는 거다.
그래서 만약 새로 들어오는 게 더 높으면, 스택 탑의 정답을 새로운 인덱스로 저장을 해주고, 팝을 해준다. 이걸 스택 탑의 높이가 새로운 인덱스의 높이보다 더 높을 때까지 반복해준다.
(같은 경우도 팝을 해 주어야 한다. 그래도 문제 조건을 만족하니까)
이러면 스택의 탑에는 계속해서 높은 원소가 남게 되니까, 더 높은 값을 찾을 수 있다.
코드는 다음과 같다.
//탑 - 골드 5
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
int n;
vector<int> h, ans;
stack<int> s;
cin >> n;
h.assign(n+1, 0);
ans.assign(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
s.push(n);
for (int i = n-1; i >= 1; i--) {
while (!s.empty() && h[i] >= h[s.top()]) {
ans[s.top()] = i;
s.pop();
}
s.push(i);
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
}참고로 이거 풀었을 때 segfault 떠서 대체 왜...? 했는데 스택이 비었을 때를 생각 안해서 그런 거였다. (새로 들어온 인덱스가 높이가 짱짱 높아서 스택에 있던 모든 원소를 날려버린 후에 스택 탑을 확인하려고 하면 아무래도 오류가 나겠지...?)
그래서 그거 고치니까 해결됐다!
옥상 정원 꾸미기
탑 풀고 다음은 이거 풀어야지~ 하고 생각만 하고 미루다가 스터디에서 추천받아서 풀게 된 문제이다.
탑 푼지 얼마 안 돼서 그나마 금방 풀었다ㅋㅋㅋ 아이디어가 거의 동일하기 때문에 뭐...
탑은 방향이 왼쪽이었다면 이건 오른쪽이고, 탑에서는 인덱스를 구하는 거였다면 이거는 나보다 낮은 탑의 개수를 구하는 문제이다.
이렇게 정리해보니까 더 비슷한 문제 같다. 아무래도... 그럴만도
마찬가지로 인덱스를 계속 넣어주는데, 나보다 높은 빌딩이 새로 들어오면 탑이 그 빌딩보다 높이가 높을 때까지 계속 팝해준다. 근데 여기서는 팝 해주면서 새로운 인덱스랑 나의 거리를 계산해서 정답에 더해준다. 그게 나랑 새로운 빌딩 사이에 존재하는 빌딩의 수니까~
그리고 또 여기서는 오른쪽 방향을 보고 있기 때문에 탐색을 왼쪽부터 오른쪽 방향으로 해주어야 한다. 따라서 처음에 0번 인덱스를 넣고, 1에서부터 n-1까지 탐색을 진행한다.
이 문제의 또 다른 차이점은 스택을 다 집어넣고 마지막에도 한 번 더 처리를 해주어야 한다는 점이다. 위 과정이 끝나면 스택에 들어있는 원소들은 높이가 낮은 순서에서 높은 순서로 정렬된 채로 들어가있는 상태이다. 근데 탑이었으면 그냥 그 높은 원소들은 답이 0이고 끝이었을텐데(나보다 높은 원소가 앞에 하나도 없으니까. 팝이 안 됐다는 건 그 뜻이다) 여기서는 나보다 낮은 빌딩의 개수를 세어주는 것이 목적이기 때문에 또 계산을 해 주어야 한다.
따라서 맨 위에 있는 가장 높이가 낮은 빌딩의 인덱스를 기억을 해주고, 한 번 팝 한 다음에 스택이 빌 때까지 계속 팝을 한다. 그 때 정답에 저장한 인덱스랑 탑과의 거리를 또 계산해서 정답에 저장해준다. 그러면 끝~
// 옥상 정원 꾸미기 - 골드 5
#include <bits/stdc++.h>
using namespace std;
int n;
long long answer;
vector<int> h, ans;
stack<int> s;
void solve() {
s.push(0);
for (int i = 1; i < n; i++) {
//다음 빌딩이 높이가 더 높거나 같으면 -> 더 높이가 높은 빌딩이 나올 때까지 pop, 확인할 수 있는 빌딩의 개수 계산 (두 인덱스 차 -1)
while (!s.empty() && h[s.top()] <= h[i]) {
answer += (i - s.top()) -1;
s.pop();
}
s.push(i);
}
int t = s.top();
s.pop();
while (!s.empty()) {
answer += (t - s.top());
s.pop();
}
}
int main() {
cin >> n;
h.assign(n, 0);
ans.assign(n, 0);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
solve();
cout << answer;
}고수들이 뭔가 문제 풀면 이렇게 다 전역변수로 빼고 main 코드도 solve 함수 하나 만들어서 거기에다가 다 쓰길래 따라해봤다ㅋㅋㅋㅋㅋㅋㅋㅋ
근데 얘도 처음 풀었을 때는 틀렸다... answer 범위 int로 해서
빌딩이 8만개까지 가능한데, 이게 내림차순으로 정렬되어있다고 생각하면 1+2+...+79999가 정답이니까... 굳이 계산을 하자면 약 32억. 무조건 오버플로우.
그래서 long long으로 안전하게 선언을 해주면 된다~
내가 스택 문제를 풀던 건 사실 이 문제를 해결하기 위해서였다.
오아시스 재결합
얘도 결국 입력 엄청 크고 높이 물어보는 거니까 비슷하긴 한데 모든 순서쌍을 구해야 하는 게 좀... 골치 아프다...
그래도 언젠가는 풀 수 있겠지?
요즘 들어서 골드 4~5 정도는 그래도 넉넉잡아서 1시간이면 풀 수 있는 정도로 올라온 것 같다. ㅎㅎ
좀 더 노력해서 플래 문제 건들여볼 수 있을 정도로 실력을 키워봐야겠다~
