[G3] 백준 17299번 오등큰수 C++ 스택

리뷰

 

최대 크기는 상관없으나 원소가 100만까지 들어올 수 있으므로 배열크기를 100만 이상으로 해야한다. ㅠㅠ

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

 

전역 변수

• n : 입력되는 수열의 길이
• lst : 입력된 수열이 저장될 배열, 크기는 100만보다 크게 해준다.
• v : 입력된 수의 개수를 저장할 배열, 크기는 100만보다 크게 해주던가 해시맵을 사용해 주자
• ans : 정답을 저장하고 출력할 배열, 크기는 100만보다 크게 해준다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 길이 n의 수열 정보를 lst배열에 입력받아준다, 입력 받은 수의 개수를 v배열을 통해 증가시킨다.
2. 빈 정수형 벡터 s를 초기화 해준다. 해당 벡터를 스택처럼 사용할 것이다.
3. 수열의 뒤에서부터 순회를하며 스택이 비지 않았을때 스택의 맨뒤 숫자와 현재 숫자의 개수를 비교해준다.
4. 만약 스택의 맨 뒤 숫자가 개수와 현재 숫자의 개수가 작거나 같으면 pop을 진행하는 작업을 반복해준다.
5. 만약 스택이 빈 상태라면 현재 인덱스의 ans배열에 -1을 입력해 준다.
6. 만약 스택이 비지 않았다면 스택의 맨 뒤 숫자를 현재 인덱스의 ans배열에 입력해 준다.
7. 스택에 현재 숫자를 추가해 준다.
8. 위 작업을 반복한 뒤 ans에 저장된 값들을 출력해 주면 된다.

 

참고 사항

1. v는 입력된 숫자의 개수를 저장하므로 100만이 들어올 경우를 처리하기 위해 100만보다 크게 해주는 것이다.
2. ans에는 스택의 사이즈가 아닌 바로 오른쪽의 수를 입력해 주어야 하기에 back을 입력한것이다.
3. 문제를 이해하기가 조금 난이했다, 문제를 잘 읽어보는걸 추천한다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
int n, lst[1000001], v[1000001], ans[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
		v[lst[i]]++;
	}
	vector<int> s;
	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && v[s.back()] <= v[lst[i]]) s.pop_back();
		if (s.empty()) ans[i] = -1;
		else ans[i] = s.back();
		s.push_back(lst[i]);
	}
	for (int i = 0; i < n; i++) cout << ans[i] << " ";
}