#include <iostream>
#include <stack>

#define X first
#define Y second

using namespace std;

int N;
stack<pair<int, int>> tower;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	tower.push({ 100000001, 0 }); // 넘을 수 없는 최대치의 벽 미리 삽입
	for (int i = 1; i <= N; i++) { // 인덱스 출력을 위해 1부터 시작
		int height;
		cin >> height;
		while (tower.top().X < height) // 더 높은 이전타워 탐색
			tower.pop();
		cout << tower.top().Y << " "; // 더 높은 타워의 레이저 송수신 결과
		tower.push({ height, i }); // 현재 타워 스택에 추가
	}
}

바킹독님의 소스. 나중에 다시 리벤지 하는걸로

핵심은 스택에 맨 먼저 넘을수 없는 최대높이, 인덱스 0의 값을 준다

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n;
	vector<int> towers;
	vector<int> temp_towers;
	vector<int> answer;

	cin >> n;

	int data;
	for (int i = 0; i < n; ++i)
	{
		cin >> data;
		towers.push_back(data);
	}

	int count = 0;

	while (true)
	{
		int tower = towers.back();
		towers.pop_back();

		temp_towers.push_back(tower);

		//count += 1;

		if (towers.empty())
		{
			break;
		}

		while (!temp_towers.empty() && temp_towers.back() < towers.back())
		{
			answer.push_back(towers.size());
			temp_towers.pop_back();
		}

		
	}

	while (!temp_towers.empty())
	{
		answer.push_back(0);
		temp_towers.pop_back();
	}

	for (int i = 0; i < n; ++i)
	{
		cout << answer.back() << " ";
		answer.pop_back();
	}

	return 0;
}

내가 원래 작성하던 코드

#include <iostream>
#include <stack>

using namespace std;

#define MAXIMUM 1000000000

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	stack<pair<int, int>> building;
	int n;
	long long answer = 0;

	cin >> n;

	building.push({MAXIMUM + 1, 0});

	for (int i = 1; i <= n; ++i)
	{
		int h;
		cin >> h;

		if (h < building.top().first)
		{
			building.push({h, i});
		}
		else
		{
			while (h >= building.top().first)
			{
				answer += i - building.top().second - 1;
				building.pop();
			}
			building.push({ h, i });
		}

		// 남은 빌딩에 대한 처리
		if (i == n)
		{
			while (MAXIMUM >= building.top().first)
			{
				answer += i - building.top().second;
				building.pop();
			}
			break;
		}
	}

	cout << answer;

	return 0;
}

바로 위 탑의 개념을 활용함.

#include <bits/stdc++.h>
using namespace std;

int a[1000000];
int ans[1000000];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  stack<int> S;
  for (int i = n - 1; i >= 0; i--) {
    while (!S.empty() && S.top() <= a[i]) S.pop(); // 현재수보다 스택안에 있는 큰수 싹다 정리
    if (S.empty())
      ans[i] = -1;
    else
      ans[i] = S.top();
    S.push(a[i]);
  }
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}

아직 못풀어서 바킹독 해답코드 들고옴. 배열 역순으로 접근해서 기준 숫자보다 큰 숫자를 다 없앤다.

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	int answer = 0;

	deque<int> rq;
	deque<int> nums;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int data;
		cin >> data;
		nums.push_back(data);
	}

	for (int i = 1; i <= n; ++i)
	{
		rq.push_back(i);
	}

	for (int num : nums)
	{
		// algorithm 헤더에 포함. 값을 찾으면 해당 위치의 iterator를 반환. 못찾으면 end.
		// 여기에 begin을 빼면 인덱스를 알 수 있음.
		int idx = find(rq.begin(), rq.end(), num) - rq.begin();
		while (num != rq.front())
		{
			// 왼쪽으로 밀기
			if (idx < (int)rq.size() - idx)
			{
				rq.push_back(rq.front());
				rq.pop_front();
			}
			else
			{
				rq.push_front(rq.back());
				rq.pop_back();
			}
			answer++;
		}
		rq.pop_front();
	}

	cout << answer;

	return 0;
}

접근은 괜찮게 했는데 나는 인덱스를 왼쪽으로 밀면 +1, 오른쪽으로 밀면 -1인 누적값을 하나 사용해서 덱사

이즈/2에 더해줘서 구해줬더니 정답이 아니길래 해답을 봤음.

코드 딱 두줄 추가하고 정답처리 받긴 했는데 좀 아쉽다.