[G3] 백준 22866번 탑 보기 C++ 스택

리뷰

 

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

현재 위치에서 볼 수 있는 탑의 개수와 볼 수 있는 탑 중 가장 가깝운 탑의 인덱스를 출력하는 문제

스택을 앞 뒤로 훑어주고, 볼 수 있는 탑이 있다면 가장 가까우면서 같다면 사전순으로 앞서는 탑을 기록해 준다.

 

전역 변수

• n : 주어지는 탑의 개수를 저장할 변수
• nodes : 탑의 높이 정보를 저장하기 위한 정수형 배열 크기는 10만 1보다 크게 해준다.
• cnt : 각 위치에서 볼 수 있는 탑의 개수를 저장하기 위한 정수형 배열, 크기 상동
• idx : 각 위치에서 볼 수 있는 탑 중 가장 가까운 탑의 인덱스를 저장하기 위한 정수형 배열, 크기 상동

 

함수

없음

 

 

문제풀이

1. n을 입력 받고, 1 ~ n번의 탑의 높이를 nodes배열에 입력 받고, 각각의 idx배열의 값을 크게 설정해 둔다.
2. 정수형 벡터 stack을 초기화 하고 다시 1 ~ n번 탑 정보를 반복문을 통해 순회해 준다. (정방향)
3. 만약 stack이 비지 않았고, nodes배열의 stack의 back인덱스가 현재 수보다 같거나 작으면 제거해준다. (반복)
4. 만약 stack이 비지 않았다면, 현재 idx와 비교하여 위치가 가장 가까운 수의 인덱스로 변경해준다.
5. 현재 탑의 cnt에 stack의 size만큼 값을 증가시킨 뒤 스택에 현재 탑의 인덱스를 추가해 준다.
6. 탐색이 종료되었다면 stack을 clear해주고 n ~ 1번 탑 정보를 반복문을 통해 순회해 준다. (역방향)
7. 정방향 탐색과 로직은 동일하나 idx를 변경해 주는 경우 절댓값을 씌워준다.
8. 모든 탐색이 끝났다면 1 ~ n번의 탑을 순회하며 cnt를 출력해 준다.
9. 만약 cnt가 존재할 경우 idx에 저장된 값을 공백으로 구분하여 출력해 준다.

 

참고 사항

• 현재 수보다 작거나 같은 값을 밀어버려야 한다.
• 정방향 역방향 모두 탐색을 진행해 주어야 한다.
• 정방향 -> 역방향 순으로 탐색한다면 idx는 자동으로 오름차순 정렬된다.
• idx[i]는 n + 1같은 값이 아닌 매우 큰 값으로 설정해 주어야 된다. (이거 땜에 한번 틀림)

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

int n;
int nodes[100001];

int cnt[100001];
int idx[100001];

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> nodes[i];
		idx[i] = 1e9;
	}

	vector<int> stack;
	for (int i = 1; i <= n; i++) {
		while (!stack.empty() && nodes[stack.back()] <= nodes[i]) {
			stack.pop_back();
		}
		if (!stack.empty()) {
			if (idx[i] - i > i - stack.back()) idx[i] = stack.back();
		}
		cnt[i] += stack.size();
		stack.push_back(i);
	}

	stack.clear();
	for (int i = n; i >= 1; i--) {
		while (!stack.empty() && nodes[stack.back()] <= nodes[i]) {
			stack.pop_back();
		}
		if (!stack.empty()) {
			if (abs(idx[i] - i) > abs(i - stack.back())) idx[i] = stack.back();
		}
		cnt[i] += stack.size();
		stack.push_back(i);
	}

	for (int i = 1; i <= n; i++) {
		cout << cnt[i];
		if (cnt[i]) cout << " " << idx[i];
		cout << "\n";
	}
}