반응형
리뷰
https://www.acmicpc.net/problem/3015
만만치 않은 스택 문제였다, 메모장을 키고 여러가지 케이스를 대입하고 나서야 풀린 문제
풀고 나서 친구와 코드 리뷰를 해보니 내 코드는 딱히 좋은 풀이 방법은 아니였다.
굳이 unordered_map을 사용하지 않고, 스택을 pair로 관리하여 cnt를 관리하는 최적화가 있으니 참고하길 바란다.
+ ans만 long long타입으로 해도 된다, 난 귀찮아서 모두 long long으로 해서 메모리가 꽤 커졌다.
전역 변수
- n : 주어지는 정수의 개수
- nodes : 정수를 저장하기 위한 배열
- cnt : 스택 상에 존재하는 정수의 개수를 표시하기 위한 해시맵
- stack : 스택
함수
없음
문제풀이
- n을 입력 받고, n개의 정수를 nodes배열에 입력 받는다.
- 첫번째 인자의 개수를 증가 시키고 스택에 push해준다.
- 1 ~ n - 1번 인덱스를 순회한다.
- 만약 스택의 맨 뒤 인자와 현재 인자가 동일하다면, ans에 현재 인자의 개수를 추가한다.
- 이후 현재 인자의 개수를 증가시킨다, 만약 스택의 길이가 2이상 이라면 ans를 1만큼 증가시키고 continue해준다.
- 만약 스택의 맨 뒤 인자가 현재 인자보다 작다면, 우선 ans에 현재 인자의 개수를 증가시켜준다.
- 스택에서 현재 인자보다 작거나 같은 값들을 모두 제거해준다.
- 현재보다 작은 인자를 제거할때는 ans에 해당 인자의 개수만큼 더해주고, 해당 인자의 개수를 0으로 만든다.
- 모든 작업을 마친 후 스택의 맨 뒤 인자가 현재 인자보다 크다면 ans를 1만큼 증가시킨다.
- 만약 스택의 맨 뒤 인자가 현재 인자보다 크다면 ans를 1만큼 증가시켜준다.
- 모든 작업을 마치고 현재 인자의 개수를 증가시켜주고, 스택에 추가해 준다.
- for문이 종료되면 ans에 저장된 값을 출력해 준다.
참고 사항
나의 풀이는 시뮬레이션을 하면서 계속 사족이 붙은 좀 더러운 코드이다.
그래도 해당 문제는 직접 풀어보고 좀 더 최적화 된 코드를 참고하는 것을 추천한다.
정답 코드
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
long long n, ans;
long long nodes[555555];
unordered_map<long long, long long> cnt;
vector<long long> stack;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> nodes[i];
cnt[nodes[0]]++;
stack.push_back(nodes[0]);
for (int i = 1; i < n; ++i) {
if (stack.back() == nodes[i]) {
ans += cnt[nodes[i]];
cnt[nodes[i]]++;
if (stack.size() >= 2) ans++;
continue;
}
else if (stack.back() < nodes[i]) {
ans += cnt[nodes[i]];
while (!stack.empty() && stack.back() <= nodes[i]) {
if (stack.back() < nodes[i]) {
ans += cnt[stack.back()];
cnt[stack.back()] = 0;
}
stack.pop_back();
}
if (!stack.empty() && stack.back() > nodes[i]) ans++;
}
else ans++;
cnt[nodes[i]]++;
stack.push_back(nodes[i]);
}
cout << ans;
}
728x90
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
[G4] 백준 17144번 미세먼지 안녕! C++ 구현, 시뮬레이션 (1) | 2024.11.12 |
---|---|
[D4] SWEA [S/W 문제해결 기본] 2일차 - Ladder1 C++ 구현, 시뮬레이션, 브루트포스 알고리즘 (0) | 2024.11.11 |
[G4] 백준 14500번 테트로미노 C++ 구현, 백트래킹 (3) | 2024.11.09 |
[G3] 백준 16637번 괄호 추가하기 C++ 구현, 백트래킹 (0) | 2024.11.08 |
[P3] 백준 2820번 자동차 공장 C++ 세그먼트 트리, 오일러 경로 테크닉, 느리게 갱신되는 세그먼트 트리 (2) | 2024.11.07 |