알고리즘 공부/C++

[P5] 백준 3015번 오아시스 재결합 C++ 스택, 해시맵

마달랭 2024. 11. 11. 15:59
반응형

리뷰

 

https://www.acmicpc.net/problem/3015

만만치 않은 스택 문제였다, 메모장을 키고 여러가지 케이스를 대입하고 나서야 풀린 문제

풀고 나서 친구와 코드 리뷰를 해보니 내 코드는 딱히 좋은 풀이 방법은 아니였다.

굳이 unordered_map을 사용하지 않고, 스택을 pair로 관리하여 cnt를 관리하는 최적화가 있으니 참고하길 바란다.

 + ans만 long long타입으로 해도 된다, 난 귀찮아서 모두 long long으로 해서 메모리가 꽤 커졌다.

 

 

전역 변수

  • n : 주어지는 정수의 개수
  • nodes : 정수를 저장하기 위한 배열
  • cnt : 스택 상에 존재하는 정수의 개수를 표시하기 위한 해시맵
  • stack : 스택

 

함수

없음

 

 

문제풀이

  1. n을 입력 받고, n개의 정수를 nodes배열에 입력 받는다.
  2. 첫번째 인자의 개수를 증가 시키고 스택에 push해준다.
  3. 1 ~ n - 1번 인덱스를 순회한다.
  4. 만약 스택의 맨 뒤 인자와 현재 인자가 동일하다면, ans에 현재 인자의 개수를 추가한다.
  5. 이후 현재 인자의 개수를 증가시킨다, 만약 스택의 길이가 2이상 이라면 ans를 1만큼 증가시키고 continue해준다.
  6. 만약 스택의 맨 뒤 인자가 현재 인자보다 작다면, 우선 ans에 현재 인자의 개수를 증가시켜준다.
  7. 스택에서 현재 인자보다 작거나 같은 값들을 모두 제거해준다.
  8. 현재보다 작은 인자를 제거할때는 ans에 해당 인자의 개수만큼 더해주고, 해당 인자의 개수를 0으로 만든다.
  9. 모든 작업을 마친 후 스택의 맨 뒤 인자가 현재 인자보다 크다면 ans를 1만큼 증가시킨다.
  10. 만약 스택의 맨 뒤 인자가 현재 인자보다 크다면 ans를 1만큼 증가시켜준다.
  11. 모든 작업을 마치고 현재 인자의 개수를 증가시켜주고, 스택에 추가해 준다.
  12. 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
반응형