BOJ 3015. 오아시스 재결합
랭크 : 골드1
문제 풀이
들어올 때 top에 있는 것 보다 작으면 쌓고, 아니면 작은 것이 나올 때까지 치우는 식으로 진행하였습니다. 수를 셀 때 여러가지 상황을 고려하였는데, 좀더 쉽게 코드를 짤 수 있을 것 같은데 너무 귀찮습니다... 세그먼트 트리를 쓰는 방법도 존재하는 것 같습니다. 중요 포인트는 같은 값이 들어왔을 때입니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
long long N, tmp, total, num, pos;
int main() {
fastio;
cin >> N;
total = 0;
vector<pair<long long, int>> arr(500'000, {0, 1});
int seeing;
cin >> tmp;
pos++;
arr[0].first = tmp;
while (--N) {
cin >> tmp;
seeing = 0;
while (pos != 0 && (arr[pos - 1].first < tmp)) {
seeing += arr[pos - 1].second;
pos--;
}
if (pos != 0 && arr[pos - 1].first == tmp) {
total += seeing + arr[pos - 1].second;
arr[pos - 1].second++;
if (pos != 1) total++;
continue;
}
if (pos) seeing++;
total += seeing;
arr[pos].first = tmp;
arr[pos].second = 1;
pos++;
}
cout << total << endl;
}
알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| 자료 구조 스택 | $O(N)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 11054. 가장 긴 바이토닉 부분 수열 (0) | 2022.07.17 |
|---|---|
| BOJ 2293. 동전 1 (0) | 2022.07.16 |
| BOJ 2629. 양팔저울 (0) | 2022.07.15 |
| BOJ 11066. 파일 합치기 (0) | 2022.07.15 |
| BOJ 1520. 내리막 길 (0) | 2022.07.15 |