#include<Dongstory.h>

조만간 업로드 

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

문제

 정수 0 ~ 9 중 하나의 수와 우선 순위가 동등한 연산자 '+, -, x' 중 하나가 차례로 나와 하나의 수식을 이룰 때, 해당 수식에 임의의 겹치지 않는 괄호를 추가해 최댓값을 구하는 문제이다.

풀이 과정

 괄호가 올 수 있는 모든 경우의 수를 완전 탐색했다. 괄호가 쳐진 것은 used_oper 배열에 표시하고, 괄호를 치기 전 해당 연산자 이전, 이후 연산자 중 괄호가 쳐진 것이 있다면 숫자가 겹치므로 다음으로 continue 했다. 괄호의 수가 정해진 것이 아니므로 다른 탈출 조건은 주지 않았고, 모든 경우의 수에서 해당 상태의 수식을 계산하며 최댓값을 갱신했다.

수식을 계산할 때는 nums, opers, used_oper을 이용해 새로운 nums_temp와 opers_temp를 만들고 계산했다. 만약 괄호가 쳐진 곳이 아니라면 계속해서 nums_temp와 opers_temp에 값을 넣어주고, 괄호가 쳐진 곳은 oper함수로 연산을 수행한 값을 nums_temp에 넣고 다음 opers값을 opers_temp에 넣었다. 그리고 인덱스가 전체적으로 한번 건너갔으므로 i를 추가로 증가시켜줬다. nums_temp와 opers_temp가 완성된 후에는 모든 연산자의 우선 순위가 동등하므로 차례로 계산해 값을 구했다.

느낀 점

 여러 인덱스들을 설정하는 과정에서 범위가 초과되는 것을 계속해서 디버깅해보며 수정했다. 오랜만에 문제를 풀다보니 범위에 대한 감이 모호해진 것 같다. 그리고 해당 문제의 값이 음수가 될 수도 있는데, ret을 0으로 두고 풀어 오답을 받기도 했다. 최대 최소를 구할 때는 문제 답의 범위를 생각해보고 알맞은 값으로 초기화를 잘해주자. 최대값을 구할 때는 문제의 최소값 이하의 값으로, 최소값을 구할 때는 문제의 최댓값 이상의 값으로 초기화를 해주자.

 문제를 푸는데 너무 오랜 시간이 걸렸다. 전체적인 틀은 금세 떠올랐지만 맵이나 그래프가 아닌 새로운 형태의 탐색에 취약했던 것 같다. 나에게는 큰 틀을 여러 곳에 응용하는 훈련이 되어서 좋은 문제였다.

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

int n, ret = -987654321;
char temp;
vector<int> nums;
vector<char> opers;
bool used_oper[9];

//연산자 함수
int oper(int a, int b, char oper) {
	if (oper == '+') return a + b;
	else if (oper == '-') return a - b;
	return a * b;
}
//used_oper을 기준으로 현재 상태의 값 연산
int calcul() {
	//괄호를 기준으로 새로운 nums_temp와 opers_temp (새로운 수식)을 구함
	vector<int> nums_temp;
	vector<char> opers_temp;
	int val = 0;
	for (int i = 0; i < n / 2; i++) {
		if (!used_oper[i]) {
			nums_temp.push_back(nums[i]);
			opers_temp.push_back(opers[i]);
		}
		else {
			nums_temp.push_back(oper(nums[i], nums[i + 1], opers[i]));
			if (i < n / 2 - 1) opers_temp.push_back(opers[i + 1]);
			i++; //한 단계씩 건너뛰었으므로
		}
	}
	//마지막 수 추가
	if (nums_temp.size() == opers_temp.size()) nums_temp.push_back(nums[n / 2]);
	//구한 수식을 기준으로 연산
	val = nums_temp[0];
	for (int i = 0; i < opers_temp.size(); i++) {
		val = oper(val, nums_temp[i + 1], opers_temp[i]);
	}
	return val;
}

//괄호가 올 수 있는 모든 경우의 수 탐색
void go(int idx) {
	//현 상태값 계산 후 최댓값 갱신
	int cur = calcul();
	ret = max(ret, cur);
	//모든 경우의 수 탐색, 불가능한 경우 continue;
	for (int i = idx; i < n / 2; i++) {
		if (idx == 0) {
			if (used_oper[i + 1]) continue;
		}
		else if (idx == n / 2 - 1) {
			if (used_oper[i - 1]) continue;
		}
		else {
			if (used_oper[i - 1] || used_oper[i + 1]) continue;
		}
		//방문
		used_oper[i] = true;
		//다음 인덱스부터 재탐색
		go(i + 1);
		//원상 복구
		used_oper[i] = false;
	}

	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		if (i % 2 == 0) nums.push_back(atoi(&temp));
		else opers.push_back(temp);
	}
	//함수 실행
	go(0);
	//출력
	cout << ret;

	return 0;
}

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

문제

 SCV가 1 ~ 3대가 있을 때, 뮤탈 리스크가 최소 몇 번을 해야 모든 SCV를 파괴할 수 있는지를 구하는 문제다. 뮤탈리스크가 한번 공격하면 9, 3, 1의 데미지가 각 SCV에게 무작위로 들어간다.

풀이 과정

 완전 탐색을 이용했다. 공격할 때 9, 3, 1의 데미지가 랜덤하게 오기 때문에 모든 경우의 수 배열로 만들었다. 이 배열을 이용해서 다음 노드를 탐색하게 된다. 이때 배열의 인덱스가 음수가 되면 안되므로 음수일 경우 0으로 처리해준다. visited에 인덱스는 '[A SCV체력][B SCV 체력][C SCV체력]' 를 의미하게 된다. 해당 체력인 경우의 수에 왔었는지 체크하고 이전 visited에  1을 더해줌으로서 최단 거리를 구한다. 최종적으로 visited[0][0][0]에 도착하게 되면 모든 SCV가 파괴된 것으로 while문을 break로 탈출한다. 출력할 때는 처음 visited가 1부터 시작했으므로 1을 빼고 출력한다.

 SCV가 3대가 아닐 경우를 위해 어떻게 처리해야할지 고민해보았다. SCV 3대를 0으로 초기화되어 있다면 문제 없다는 것을 알았다. SCV의 값이 별도로 입력되지 않으면, 0인 값을 가지고 이미 파괴된 상태이기 때문에 최종 해에 영향을 미치지 않는다.

느낀 점

 처음 풀 때는 단순히 체력이 큰 SCV를 우선으로 타겟하는 식으로 문제를 풀었다. 하지만 모든 경우 최적의 해를 구할 수 없었던 기억이 있다. 이후 문제 푼지가 꽤 되어서 기억이 아에 나지 않았는데, 천천히 생각하다 보니 BFS를 이용한 완전 탐색이 떠올랐고, visited 배열을 이용해 인덱스를 기록하는 방법이 떠올랐다. 조금은 체화된 것 같아서 기뻤다. BFS와 DFS를 이용한 완전 탐색만 자유자제로 적용할 수 있어도 꽤 많은 문제를 풀 수 있을 것 같다. 앞으로도 복습을 꾸준히 해가도록 하자.

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

//공격하는 모든 경우의 수
int atk[6][3] = {
	{9, 3, 1},
	{9, 1, 3},
	{3, 9, 1},
	{3, 1, 9},
	{1, 9, 3},
	{1, 3, 9}
};
//SCV 체력 데이터 입력을 위한 구조체
struct scvs {
	int a, b, c;
};
//방문 처리를 위한 배열
int visited[64][64][64];

//3개 이하의 scv가 입력되었을 때도 0으로 초기화되어 있으므로 무관
int n, scv[3];
queue<scvs> q;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> scv[i];
	}

	//BFS
	q.push({ scv[0], scv[1], scv[2] });
	visited[scv[0]][scv[1]][scv[2]] = 1; //이때 1부터 시작했기 때문에 출력 때 1을 빼준다.
	while (q.size()){
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();
		//다음 공격 경우의 수 탐색
		for (int i = 0; i < 6; i++) {
			int na = a - atk[i][0];
			int nb = b - atk[i][1];
			int nc = c - atk[i][2];
			//배열 인덱스가 음수가 되면 안되므로 0 처리
			if (na < 0) na = 0;
			if (nb < 0) nb = 0;
			if (nc < 0) nc = 0;
			if (visited[na][nb][nc]) continue;
			//최단 거리를 구하기 위한 이전 visited + 1
			visited[na][nb][nc] = visited[a][b][c] + 1;
			q.push({ na, nb, nc });
		}
		//모든 SCV가 파괴되었다면 탈출
		if (visited[0][0][0]) break;
	}

	//출력
	cout << visited[0][0][0] - 1;

	return 0;
}

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

풀이 과정

 매 시간 불이 사방으로 번지고 지훈이는 사방으로 한 칸씩 이동할 때 지훈이가 몇 번의 이동만에 탈출 할 수 있는지 구하는 문제이다.

 BFS로 지훈의 시간과 불이 번지는 시간을 구한다. 불은 여러 개가 존재 할 수 있으므로 입력시 큐에 넣고 이어서 BFS로 탐색한다. 그리고 지훈이가 테두리에 위치할 경우 바로 탈출이 가능하므로 처음 입력 시 검사가 필요하고, BFS로 지훈이가 불보다 빠를 때만 이동하도록 해서 시간을 구했다.

느낀 점

 처음에 설계를 잘못해서 곤혹을 치뤘다. 불이 여러 개 있다는 것을 고려하지 못하고 사람BFS와 불BFS를 하나로 구현하려고 하다보니 생긴 문제였다. 이럴 때는 과감하게 처음부터 다시 설계를 해보는게 필요할 것 같다.

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

const int MX = 1004, INF = 99999999;
int mp[MX][MX], person[MX][MX], fire[MX][MX];
int n, m, ret;
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
pair<int, int> sp;
char temp;
queue<pair<int, int>> q;

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp == '#') mp[i][j] = 1;
			else if (temp == '.') mp[i][j] = 0;
			else if (temp == 'F')
			{
				fire[i][j] = 1;
				q.push({ i, j });
			}
			else if (temp == 'J') sp = { i, j };
		}
	}
	return;
}


void output() {
	if (ret == 0) cout << "IMPOSSIBLE\n";
	else cout << ret << "\n"; //최종 탈출을 위한 ++
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	fill(&fire[0][0], &fire[0][0] + MX * MX, INF);
	input();

	//불 좌표마다 BFS 실행
	while (q.size()) {
		int fy = q.front().first;
		int fx = q.front().second;
		q.pop();
		for (int v = 0; v < 4; v++) {
			int ny = my[v] + fy;
			int nx = mx[v] + fx;
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || mp[ny][nx]) continue;
			if (fire[ny][nx] != INF) continue;
			fire[ny][nx] = fire[fy][fx] + 1;
			q.push({ ny, nx });
		}
	}

	/*
	cout << "\nfire info\n";
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << fire[i][j] << " ";
		}
		cout << "\n";
	}
	*/


	//사람 BFS 실행
	person[sp.first][sp.second] = 1;
	q.push({ sp.first, sp.second });
	while (q.size()) {
		int fy = q.front().first;
		int fx = q.front().second;
		q.pop();
		if (fy == n - 1 || fy == 0 || fx == m - 1 || fx == 0) {
			//cout << "ans fy fx : " << fy << ", " << fx << "\n";
			ret = person[fy][fx];
			break;
		}
		for (int v = 0; v < 4; v++) {
			int ny = my[v] + fy;
			int nx = mx[v] + fx;
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || mp[ny][nx] || person[ny][nx]) continue;
			if (fire[ny][nx] <= person[fy][fx] + 1) continue;
			//cout << "ny , nx : " << ny << ", " << nx << "\n";
			person[ny][nx] = person[fy][fx] + 1;
			q.push({ ny, nx });
		}
	}
	/*
	cout << "\nperson info\n";
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << person[i][j] << " ";
		}
		cout << "\n";
	}
	*/


	//결과 출력
	output();

	return 0;
}

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

풀이 과정

 인구 차가 주어진 범위 내에 있는 국가들은 연결되고 연결된 국가들의 값이 연결된 국가들의 인구의 평균으로 바뀌고 하루가 지난다. 몇 일이 지나야 인구 이동이 끝나는지를 구하는 문제이다.

 하루에 한번  모든 그래프의 인구 이동과 평균을 해주기 위해서 while문에서 매번 day를 더해주고 visited를 초기화 해준다. 

 매일 모든 나라를 방문하며 연결 컴포넌트를 구한다. 연결 컴포넌트를 구할 때 범위 내에 있어야 한다는 조건을 추가한다. 한 연결 컴포넌트를 순회하면서 union_list에 좌표를 기록한다. 방문이 끝나면 연결 컴포넌트의 평균을 구하고 union_list 좌표가 가르키는 값에 평균값을 대입한다. 이때 값이 다르다면 변화가 있었던 것으로 changed_flag를 true로 바꿔준다.

 이후 변화가 없을 때 changed_flag가 false가 되며 while문을 탈출한다. 마지막 변화가 없는 날 하루를 더 관찰했으므로 day에서 하루를 빼고 출력한다.

느낀 점

 매번 바뀌는 연결 컴포넌트 구조를 만들며 몇 번까지 바뀌는지 구하는 문제였다. 시뮬레이션 문제는 큰 틀을 잡고 안에 세세한 조건을 잘 추가해주는 것이 중요한 것 같다.

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

const int MAX = 54;
int visited[MAX][MAX], mp[MAX][MAX];
int n, bot, top, sum, cnt, day;
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> union_list;
bool changed_flag = true;

//기록된 노드 평균으로 채우기
void fill_avg(int fill) {
	for (int i = 0; i < union_list.size(); i++) {
		int y = union_list[i].first;
		int x = union_list[i].second;
		if(mp[y][x] != fill) changed_flag = true;
		mp[y][x] = fill;
	}
	return;
}

//탐색 하며 노드 기록
void DFS(int y, int x) {
	union_list.push_back({ y, x });
	sum += mp[y][x];
	visited[y][x] = 1;
	for (int d = 0; d < 4; d++) {
		int ny = my[d] + y;
		int nx = mx[d] + x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
		//인구 차이 조건
		int gab = abs(mp[y][x] - mp[ny][nx]);
		if (gab < bot || gab > top) continue;
		DFS(ny, nx);
	}
	cnt++;
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n >> bot >> top;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mp[i][j];
		}
	}

	//멈출 때 까지 반복
	do {
		changed_flag = false; day++;
		fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				sum = 0; cnt = 0; union_list.clear();
				DFS(i, j);
				fill_avg(sum / cnt);
			}
		}
		/* 테스트 출력
		cout << "인구 이동 후 \n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << mp[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
		*/
	} while (changed_flag);

	cout << day - 1;

	return 0;
}

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

풀이 과정

 4방향 그래프에서 육지인 곳 중, 최단 거리가 가장 큰 곳의 거리를 구하는 문제이다. 우선 입력을 받고, 모든 노드를 탐색하며 (탐색할 때마다 visited 초기화) visited의 최댓값을 구하며 ret을 최댓값으로 갱신했다.

느낀 점

 기본적인 BFS를 이용한 최단 거리 문제이다.

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

const int MAX = 53;
int visited[MAX][MAX], mp[MAX][MAX];
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
int n, m, ret;
char temp;

//BFS로 탐색하며 최대 visited[][]로 ret갱신
void BFS(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (q.size()) {
		int now_y = q.front().first;
		int now_x = q.front().second;
		for (int i = 0; i < 4; i++) {
			int ny = now_y + my[i];
			int nx = now_x + mx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || !mp[ny][nx])continue;
			visited[ny][nx] = visited[now_y][now_x] + 1;
			ret = max(ret, visited[ny][nx] - 1);
			q.push({ ny, nx });
		}
		q.pop();
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp == 'W') mp[i][j] = 0;
			else mp[i][j] = 1;
		}
	}

	//모든 노드 탐색
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!mp[i][j]) continue; //육지일 경우에만 탐색
			fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
			BFS(i, j); //BFS 탐색
		}
	}
	
	//출력
	cout << ret;

	return 0;
}

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

풀이 과정

 치킨집들 중 m개를 뽑고, 해당 경우의 수 일 때 도시의 치킨 거리를 구한다. 이때 최소 치킨 거리를 구하는 문제이다. 치킨 거리는 집과 치킨집의 최단 거리를 말한다.

느낀 점

 역시 머릿 속에 로직이 있으니 첫 구현은 간단했다. 하지만 2번의 막힘이 있었다.

 첫 번째는 조합을 구현할 때 combi() 함수의 인자를 i가 아닌 idx로 주어서 같은 값이 여러번 중복되어 나타났다. 처음 풀 때도 같은 실수를 한 걸 생각하면 조합 구현이 아직 미숙한 것 같다. 그 때와 같이 조합값을 디버깅하며 검사하다가 발견했다.

 두 번째는 문제에서 최댓값을 잘못 파악했다. n의 최댓값은 50이고 m의 최댓값은 13이다. 하지만 n의 최댓값을 13으로 보고, MAX를 13으로 설정해줘서 오답을 받았다. 기본적인 실수임에도 문제를 다시 읽지는 않아서 파악하는데 오래 걸렸다. 이전에 소스 코드를 보고 비교하던 중, 이전 코드에는 NMAX라는 값을 따로 할당해준 것을 보고 알아차렸다. 디버깅 값이 모두 맞고 어디서 잘못된 것인지 모를때는 문제의 조건을 잘못 파악하지는 않았는지 생각하며 문제를 다시 보자. 

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

const int MAX = 50;
int n, m, cnt, ret, min_dis = 2098765432;
int mp[MAX][MAX], visited[MAX][MAX], dis[MAX][MAX];
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> chicken, home, com;

//BFS로 탐색하며 visited에 거리 저장
void BFS(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (q.size()) {
		int nowy = q.front().first;
		int nowx = q.front().second;
		q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = my[d] + nowy;
			int nx = mx[d] + nowx;
			if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
			visited[ny][nx] = visited[nowy][nowx] + 1;
			q.push({ ny, nx });
		}
	}
	return;
}

//경우의 수를 구하고, 해당 경우에서 최소 치킨 거리를 갱신
void combi(int idx) {
	if (com.size() == m) {
		//경우의 수 생성, com의 치킨집 좌표 마다 BFS 실행
		int sum = 0;
		fill(&dis[0][0], &dis[0][0] + MAX * MAX, 2098765432);
		for (int i = 0; i < com.size(); i++) {
			fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
			BFS(com[i].first, com[i].second);
			//visited 와 dis min()을 통해 갱신
			for (int j = 0; j < home.size(); j++) {
				int hy = home[j].first;
				int hx = home[j].second;
				dis[hy][hx] = min(dis[hy][hx], visited[hy][hx] - 1);
			}
		}

		//치킨 거리 합 구하고 최소값 갱신
		for (int i = 0; i < home.size(); i ++) {
			sum += dis[home[i].first][home[i].second];
		}
		min_dis = min(min_dis, sum);

		return;
	}

	for (int i = idx + 1; i < chicken.size(); i++) {
		com.push_back(chicken[i]);
		combi(i);
		com.pop_back();
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++){
			cin >> mp[i][j];
			if (mp[i][j] == 2) chicken.push_back({ i, j });
			if (mp[i][j] == 1) home.push_back({i, j});
		}
	}

	combi(-1);

	cout << min_dis;

	return 0;
}

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

풀이 과정

 수열을 입력 받고, 수열의 어떤 수 보다 큰 수 중, 수열의 오른쪽에 가장 가까이 위치한 수를 오큰수라고 한다. 오큰수가 있다면 오큰수를, 없다면 -1을 출력하는 문제이다.

 스택을 이용했다. 스택에 수열을 넣고 새로 입력받은 값으 이미 입력된, 스택에 있는, 값에 대한 오큰수가 될 수 있는지 비교하면서 오큰수라면 ret배열에 값을 넣어주고 stk에서 pop() 했다. ret의 초기 값이 -1이기 때문에 오큰수가 없는 경우 -1로 출력 된다.

느낀 점

 스택 문제라는 걸 생각하면 푸는 건 금방인 문제이다. 하지만 처음에 스택이라는 사실을 떠올리기 어려웠다. 문제를 보고 유형을 파악하는 게 얼마나 중요한지 보여준 문제이다.

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

int n, temp;
stack<pair<int, int>> stk; //값, 번호
int ret[1000004];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력 수 입력
	cin >> n;
	
	//입력 받으며 동시에 스택에서 처리
	fill(&ret[0], &ret[0] + 1000004, -1); //오큰수가 없을 때 초기값 -1
	for (int i = 0; i < n; i++) {
		cin >> temp;
		//스택이 비어있지 않고, 스택 탑이 입력 값보다 작다면 입력 갑싱 오큰수
		while (!stk.empty() && stk.top().first < temp) {
			ret[stk.top().second] = temp; //인덱스에 오큰수 기록
			stk.pop();
		}
		stk.push({ temp, i });
	}

	//출력
	for (int i = 0; i < n; i++) {
		cout << ret[i] << " ";
	}

	return 0;
}