pushback

브루트포스 문제이다.

백트래킹을 사용하여 모든 경우를 탐색해주자. 

연산자 개수가 10개 밖에 안돼서 next_permutation으로 해결하는 방법도 있다.

1. 백트래킹

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

int n;
int num[12];
int cal[4];
int maxANS = -1'000'000'001; // 답의 범위는 -10억 ~ 10억
int minANS = 1'000'000'001;

void recur(int sum, int cur) {
	// 한번의 탐색이 끝나면, 최댓값 최솟값 갱신
	if (cur == n) {
		maxANS = max(maxANS, sum);
		minANS = min(minANS, sum);
		return;
	}

	for (int i = 0; i < 4; ++i) {
		// i번 연산자가 남아있지 않은 경우 다음 연산자로 넘어감
		if (cal[i] == 0) continue;
        
		// i번 연산자를 1개 사용
		--cal[i];
		if (i == 0) recur(sum + num[cur], cur + 1);
		else if (i == 1) recur(sum - num[cur], cur + 1);
		else if (i == 2) recur(sum * num[cur], cur + 1);
		else if (i == 3) recur(sum / num[cur], cur + 1);
        
		// 사용이 끝났으니 사용한 연산자 반납
		++cal[i];
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> num[i];
	for (int i = 0; i < 4; ++i) cin >> cal[i];
	
	recur(num[0], 1);
	cout << maxANS << '\n' << minANS;
	return 0;
}

2. next_permutation()

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

int num[11];
int maxANS = -1'000'000'001;
int minANS = 1'000'000'001;
vector<int> calc;

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

	int n, numOfCases;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];
        
	// 연산자 나열
	for (int i = 0; i < 4; i++)
	{
		cin >> numOfCases;
		while (numOfCases--) calc.push_back(i);
	}

	// 나올 수 있는 경우의 수 계산 == 팩토리얼 연산
	numOfCases = 1;
	for (int i = 1; i <= n - 1; i++) numOfCases *= i; 
	
	while(numOfCases--) {
		int tmp = num[0];
		for (int j = 1; j < n; j++)
		{
			switch (calc[j - 1])
			{
			case 0:
				tmp += num[j];
				break;
			case 1:
				tmp -= num[j];
				break;
			case 2:
				tmp *= num[j];
				break;
			case 3:
				tmp /= num[j];
				break;
			}
		}
		minANS = min(minANS, tmp);
		maxANS = max(maxANS, tmp);
		next_permutation(calc.begin(), calc.end()); // 다음 경우
	}

	cout << maxANS << '\n' << minANS;

	return 0;
}

가능하다고 했지 빠르다곤 안했다.. ㅎㅎ

백트래킹은 중간 연산 결과를 이용할 수 있어서 속도가 빠르지만,

이 풀이는 매 경우마다 계산을 다 해주어야해서 당연히 속도가 느리다.

백트래킹으로 빈칸마다 들어갈 수 있는 수를 찾아 넣어주자.

그러다보면 빈칸임에도 불구하고 넣을 수 있는 숫자가 없는 경우가 있다.

이 경우엔 앞에서 잘못된 숫자가 들어간 것이기 때문에, 다시 뒤로 돌아가자.

\((x, y)\)번째 칸에 넣을 수를 찾는 방법은 1부터 9까지 돌면서

1. \(x\)번째 행에 어떤 수 \(n\)이 존재하는지
2. \(y\)번째 열에 어떤 수 \(n\)이 존재하는지
3. \(((x / 3), (y / 3))\)번 정사각형 안에 어떤 수 n이 존재하는지 (하단 그림 참조)

   

확인해주면 된다.

1. bool 배열로 구현

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

int sudoku[9][9];
bool row[9][10]; // 행
bool col[9][10]; // 열
bool block[3][3][10]; // 3x3 정사각형
vector<pair<int, int>> blank; // 빈칸들의 좌표

void recur(int cur) {
	// 모든 칸이 채워졌다면 출력 후, exit(0)을 통해 바로 프로그램 종료
	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		// i라는 숫자가 현재 칸이 속한 행, 열, 3x3 정사각형 안에 존재하는 지 확인
		// 한 곳이라도 존재하면 다음 숫자로 넘어감
		if (row[x][i] || col[y][i] || block[x / 3][y / 3][i]) continue;

		// (x, y)에 i라는 숫자를 채워넣음
		row[x][i] = true;
		col[y][i] = true;
		block[x / 3][y / 3][i] = true;
		sudoku[x][y] = i;
        
		recur(cur + 1); // 다음 칸으로 넘어가기
		
		// 호출한 재귀함수가 리턴됐다는 것은, 현재 빈칸에 i라는 숫자가 들어가면 안된다는 의미
		// 다른 숫자를 채워넣기 위해, (x, y)에서 i라는 숫자를 제거
		row[x][i] = false;
		col[y][i] = false;
		block[x / 3][y / 3][i] = false;
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		// 입력받은 수를 행, 열, 3x3 정사각형에 추가
		row[i][sudoku[i][j]] = true;
		col[j][sudoku[i][j]] = true;
		block[i / 3][j / 3][sudoku[i][j]] = true;

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

2. 비트 연산으로 구현

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

int sudoku[9][9];
int row[9];
int col[9];
int block[3][3];
vector<pair<int, int>> blank;

void recur(int cur) {

	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		int bit = (1 << i);

		if ((row[x] & bit) || (col[y] & bit) || (block[x / 3][y / 3] & bit)) continue;

		row[x] |= bit;
		col[y] |= bit;
		block[x / 3][y / 3] |= bit;
		sudoku[x][y] = i;
		recur(cur + 1);
		
		row[x] &= (~bit);
		col[y] &= (~bit);
		block[x / 3][y / 3] &= (~bit);
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		row[i] |= (1 << sudoku[i][j]);
		col[j] |= (1 << sudoku[i][j]);
		block[i / 3][j / 3] |= (1 << sudoku[i][j]);

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

bit연산으로 구현하면 빨라질까 해서 구현해봤지만.. 아무래도 메모리접근 한번보다는 비트연산의 비용이 더 비싼 것 같다.

너무나도 유명한 문제이다.

세상에 수많은 풀이 방법이 공개되어있으니 한번 검색해보는 것을 추천한다.

이 문제는 널널한 시간을 줬음에도 불구하고, 아무생각 없이 모든 경우를 탐색하면 시간초과이다.

여기서 내가 말하는 모든 경우 탐색이란, Queen을 같은 칸이 아닌 곳에 일단 박아놓고 Queen끼리 서로 공격할 수 있는지 확인하는 무지성 방법이다.

대충 시간복잡도 계산해보면,

• 퀸을 놓는 경우 = \(O( _{225}P_{15})\)
• 서로 공격할 수 있는지 확인하는 데 걸리는 시간 = \(O(15^2)\)

매 경우마다 공격할 수 있는지 확인해야하니 둘을 곱하면.... 대충 생각해봐도 어질어질한 수치이다.

그래서 이 문제는 처음부터 서로 공격하지 못하게 놓는게 포인트이다.

그렇게 하기 위해 Queen은 8방향 모두 움직일 수 있다는 특성을 이용하자.

Queen이 8방향을 다 갈 수있다 == 어떤 Queen 하나를 놓았을 때, 이 Queen이 속하는 행, 열, 대각선 2개 위에 더 이상 다른 Queen이 올라오면 안된다는 것이다.

그럼 어떻게 코딩할 것인가 ?

재귀함수는 x번 행에서 y번 열에 Queen을 놓을 수 있는지 확인한다. y번 열에 놓을 수 있는지 판단하기 위해서, (x, y)의 값을 통해

• x번 행 위에 Queen이 존재하는지
• y번 열 위에 Queen이 존재하는지
• (x, y)를 포함하고 왼쪽 위에서 오른쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지
• (x, y)를 포함하고 오른쪽 위에서 왼쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지

를 보면 된다.

만약 놓을 수 있다면, (x, y)가 속한 모든 선을 true로 바꿔주고 다른 행으로 넘어가면 된다.

대각선을 판단하는게 좀 어려울 수도 있는데, 이것만 알아두면 된다.

• 왼쪽 위에서 오른쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 - 열) 값은 모두 동일하다.
• 오른쪽 위에서 왼쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 + 열) 값은 모두 동일하다.

코드를 보자.

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

bool row[16]; // 행
bool col[16]; // 열
bool crossFromRight[31]; // 대각선 오른쪽 위에서 왼쪽 아래
bool crossFromLeft[31]; // 대각선 왼쪽 위에서 오른쪽 아래
int n;

void setFlag(int& line, int& i, bool flag) {
	row[line] = col[i] = crossFromRight[line + i] = crossFromLeft[i - line + 15] = flag;
}

void recur(int line, int& cnt) {
	// n개의 라인에 Queen을 모두 놓은 경우
	if (line == n) {
		cnt++;
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (!row[line] && !col[i] && !crossFromRight[line + i] && !crossFromLeft[i - line + 15]) {
			setFlag(line, i, true);
			recur(line + 1, cnt);
			setFlag(line, i, false);
		}
	}
}


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int cnt = 0;
	cin >> n;

	recur(0, cnt);

	cout << cnt;

	return 0;
}

내 코드는.. 좀 많이 느린 편이다. 구글링을 통해 더 빠른 코드들을 구경해보는 것도 좋을 것 같다.

0ms 걸리는 코드들은 그냥 https://oeis.org/A000170 이걸보고 바로 답을 출력한 것 같다.

비내림차순.. 별 거 없다. 

이전 재귀함수에서 뽑힌 숫자부터 for문을 돌려주면 된다.

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

int N, M;
string ans;

void recur(int prev, int cnt) {

	if (cnt == M) {
		ans.back() = '\n';
		cout << ans;
		return;
	}

	for (int cur = prev; cur <= N; ++cur) {
		ans += cur + '0';
		ans += ' ';
		recur(cur, cnt + 1);
		ans.pop_back();
		ans.pop_back();
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(1, 0);

	return 0;
}

중복을 신경쓰지 않기 때문에, 재귀함수 내 for문은 1부터 N까지 돌자. 재귀함수를 M번 호출하면 끝.

참고로, 답을 int형 배열이 아닌 string에 저장하면 입출력 속도가 월등히 빨라진다.

1. int형 배열에 답 저장

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

int N, M;
int ans[9];

void recur(int cnt) {

	if (cnt == M) {
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int cur = 1; cur <= N; ++cur) {
		ans[cnt] = cur;
		recur(cnt + 1);
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);

	return 0;
}

2. string에 답 저장

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

int N, M;
string ans;

void recur(int cnt) {

	if (cnt == M) {
		ans.back() = '\n';
		cout << ans;
		return;
	}

	for (int cur = 1; cur <= N; ++cur) {
		ans.push_back(cur + '0');
		ans.push_back(' ');
        
		recur(cnt + 1);
        
		ans.pop_back();
		ans.pop_back();
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);

	return 0;
}

재귀 함수를 돌 때, (이전 재귀함수에서 선택된 수 + 1) ~ N까지 for문을 돌리면 된다.

오름차순으로  출력해야되기 때문에 N과 M (1)에서 사용한 isTrue라는 bool형 배열도 필요없다.

왜 ? 선택되는 순서 자체가 오름차순이기 때문.

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

int N, M;
int ans[9];

void recur(int prev, int cnt) {

	if (cnt == M) {
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int cur = prev + 1; cur <= N; ++cur) {
		ans[cnt] = i;
		recur(cur, cnt + 1);
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0, 0);

	return 0;
}

개인적으로 백트래킹이나 브루트포스나 큰 차이가 없다고 생각한다.

그래도 백트래킹이라고 하면, 보통 재귀 함수를 통해 모든 경우의 수를 탐색하는 것을 말한다.

나중에 가지치기(pruning)라는 기법으로 탐색 시간을 줄일 수 있다.

기법이라고 해서 좀 어려워보이는데.. 그냥 조건문을 통해 더 탐색을 할 것인지 결정해주는 거라고 보면 된다.

N과 M 시리즈는 별 거 없다. 백트래킹으로 문제에서 원하는 조건만 잘 지켜주면 해결 가능하다.

코드 재사용을 통해 어떤 조건을 어떻게 바꿔야 하는지 훈련하면 좋을 것 같다.

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

int N, M;
bool isTrue[9]; // 이미 뽑힌 숫자인지 ?
int ans[9]; // 답 저장

// cnt : 몇 개가 뽑혔는지
void recur(int cnt) {
	// 원하는 개수가 다 뽑혔다면 답 출력
	if (cnt == M) { 
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}
    
	// 1 ~ N까지 돌면서 안뽑힌 숫자를 뽑고 다음 재귀함수 호출
	for (int i = 1; i <= N; ++i) {
		if (isTrue[i]) continue;

		isTrue[i] = true;
		ans[cnt] = i;
		recur(cnt + 1);
		// 호출이 끝나면 뽑힌 숫자를 놓아준다.
		isTrue[i] = false;
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);
	
	return 0;
}

문제를 읽고 그냥 정렬하면 되네~하면 안되는 문제이다. 처음 입력 받은 순서대로 답을 출력해주어야한다.

에이~ 그러면 그냥 똑같은 배열 두개 만들어서, 하나는 냅두고 다른 하나는 정렬해서 답 내면 되잖아 ㅋㅋ

그런 분들에게 말한다. 이 문제의 핵심은 "나보다 작은 수가 몇개냐?" 이다. 근데 이제 여기에 서로 다른 수가 추가된..

자, 밑에 그림과 같이 똑같은 배열 두개가 있고 하나는 정렬되어있는 상태라고 생각해보자.

입력받은 배열을 기준으로 답을 찾아 출력해보자.

1. 2 보다 작은 서로 다른 수의 개수 = 2
2. 4 보다 작은 서로 다른 수의 개수 = 3
3. -10 보다 작은 서로 다른 수의 개수 = 0
4. 4 보다 작은 서로 다른 수의 개수 = 3
5. -9 보다 작은 서로 다른 수의 개수 = 1
6. 6 보다 작은 서로 다른 수의 개수 = 4

혹시 어떻게 \(x\)보다 작은 서로 다른 수의 개수를 세었는가 ? 정렬한 배열에서 하나씩 세셨다면..

어이고... 그러면 최악의 경우에 정렬한 배열을 처음부터 끝까지 다 봐야하는 경우(=\(O(n)\))가 생긴다. 

따라서 시간복잡도가 \(O(n * n) = O(n^2)\)이 되기 때문에 시간초과될 확률이 너무나도 높다.

시간복잡도를 줄여보자. 입력받은 배열에서 한번 쭉~ 도는 것을 줄일 순 없다. 

그렇다면, 답을 찾는 시간복잡도를 \(O(n)\)에서 \(O(log n)\) 또는 \(O(1)\)으로 줄여보자.

정해라고 생각되는 \(O(1)\)부터 보자.

정렬할 배열의 구성을 좀 바꿔주자. 입력받은 수만 저장하지말고 ( 입력받은 수, index ) 같이 저장하자.

그러면 이렇게 된다.

이제부터 입력받은 배열을 답을 저장한 배열로 바꿔줄 것이다. 어떻게 ???

자, 서로 다른 수의 개수를 저장할 변수(count) 하나를 갖고 정렬한 배열을 처음부터 끝까지 쭈우욱 돌아보자.

첫번째 칸은 당연히 자신보다 작은 서로 다른 수가 없기 때문에, 바로 첫번째 칸에 들어있는 index에 접근하여 현재 서로 다른 수의 개수를 넣어주자.

두번째 칸을 보자.가장 먼저 해줄 일은 이전 칸에 저장된 값과 지금 보고 있는 칸에 저장된 값이 다른지? 이다. 

만약 다르다면, 나보다 작은 서로 다른 수의 개수가 하나 더 많아져야한다.

확인이 끝난 후 저장된 인덱스에 접근하여 현재 서로 다른 수의 개수를 저장해주면 된다.

이제 계속 똑같이 진행해주면 된다.

모든 과정이 끝나고 입력받은 배열만 출력해주면 된다.

#include <bits/stdc++.h>
using namespace std;
struct Pair {
	int number;
	int index;
	
	bool operator< (const Pair& p) {
		return this->number < p.number;
	}
};

int num[1000001]; // 입력받는 배열
Pair ordered[1000001]; // 정렬할 배열

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

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		ordered[i] = { num[i], i };
	}
	
	// 정렬
	sort(ordered, ordered + n);

	int cnt = 0;
	num[ordered[0].index] = cnt; // 첫번째 칸 채우기
    
	for (int i = 1; i < n; ++i) {
		if (ordered[i].number != ordered[i - 1].number) ++cnt; // 이전 칸과 다른 값인지 ?
		num[ordered[i].index] = cnt; // 저장된 인덱스에 접근해서 서로 다른 수의 개수 저장
	}

	for (int i = 0; i < n; ++i) cout << num[i] << ' ';

	return 0;
}

이미 \(O(1)\)에 답을 찾는 방법을 설명했기 때문에, 이 밑에 부분은 그냥 궁금한 분들만 보시면 될 것 같다.

\(O(log n)\)방법은 간단하다. 정렬한 배열에서 중복수를 제거하고 이분탐색으로 답을 낼 수 있다.

근데 중복수를 제거할 때,

(중복수인지 확인 = \(O(n)\)) * (제거하는 시간 = \(O(n)\) \(=\) \(O(n^2)\)이라서 시간복잡도가 안줄지 않냐 ? 예리하다.

그래서 세 가지 방법이 있다.

1. \(O(n logn)\)에 중복수 제거 => 배열 정렬 후에 중복되지 않은 수만 다른 vector에 추가
2. \(O(n)\)에 중복수 제거 => C++의 unique함수
3. \(O(logn)\)에 중복수 제거 => map 또는 set 컨테이너 사용

이분 탐색은 STL의 lower_bound를 이용하여 내가 원하는 수가 몇번 인덱스에 있는지 확인하면, 그 인덱스가 답이 된다.지적 유희 시간이기 때문에, unique와 lower_bound에 대해선 나중에 설명해보겠다.

1. \(O(n logn)\)에 중복수 제거

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

int num[1000001];
int ordered[1000001];
vector<int> vec;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		ordered[i] = num[i];
	}
	// 정렬
	sort(ordered, ordered + n);
	
	vec.push_back(ordered[0]);
	// 중복되지 않은 수들만 vec에 추가
	for (int i = 1; i < n; ++i) if (ordered[i] != ordered[i - 1]) vec.push_back(ordered[i]);

	for (int i = 0; i < n; ++i) cout << (int)(lower_bound(vec.begin(), vec.end(), num[i]) - vec.begin()) << ' ';

	return 0;
}

2.\(O(n)\)에 중복수 제거

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

int num[1000001];
vector<int> ordered;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	ordered.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		ordered[i] = num[i];
	}
	// 정렬
	sort(ordered.begin(), ordered.end());
	// unique를 이용해 중복 값을 모두 제거
	ordered.resize(unique(ordered.begin(), ordered.end()) - ordered.begin());
	
	for (int i = 0; i < n; ++i) cout << (int) (lower_bound(ordered.begin(), ordered.end(), num[i]) - ordered.begin()) << ' ';
	
	return 0;
}

3 - 1. \(O(logn)\)에 중복수 제거 (map container)

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

int num[1000001];
map<int, int> mp;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		mp[num[i]]++;
	}

	int cnt = 0;
	for (auto it = mp.begin(); it != mp.end(); ++it) {
		it->second = cnt++;
	}

	for (int i = 0; i < n; ++i) cout << mp[num[i]] << ' ';

	return 0;
}

3 - 2. \(O(logn)\)에 중복수 제거 (set container로 중복 제거 후, map에 답을 저장)

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

int num[1000001];
unordered_map<int, int> mp;
set<int> s;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		s.insert(num[i]);
	}

	int sum = 0;
	for (auto it = s.begin(); it != s.end(); ++it) {
		mp[*it] = sum++;
	}

	for (int i = 0; i < n; ++i) cout << mp[num[i]] << ' ';

	return 0;
}

고생의 흔적들