[C++] Inversion Sequence 🔥

📄문제

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다.
예를 들어 다음과 같은 [4 8 6 2 5 1 3 7] 수열의 경우

• 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개
• 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개
• 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개이다.

따라서 4 8 6 2 5 1 3 7의 inversion sequence는 [5 3 4 0 2 1 1 0] 이 된다.

n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 inversion sequence가 숫자 사이에 한 칸의 공백을 두고 주어진다.

8 5 3 4 0 2 1 1 0

 

⬆️ 출력

오름차순으로 정렬된 수열을 출력합니다.

4 8 6 2 5 1 3 7

 

📝 풀이

#include <iostream>
#include <vector>

int main()
{
	int N;
	scanf_s("%d", &N);

	std::vector<int> iSeq(N), res(N);
	for (int i = 0; i < N; ++i)
		scanf_s("%d", &iSeq[i]);

	// 마지막은 항상 0 (N보다 큰 수가 앞에 올 수 없음)
	res[N - 1] = N;

	// 마지막에서 한칸 앞 부터 시작
	for (int i = N - 2; i >= 0; --i)
	{
		// iSeq[i]만큼 i + j번째에 있는 값을 오른쪽에 있는 값으로부터 가져옴
		for (int j = 0; j < iSeq[i]; ++j)
			res[i + j] = res[i + j + 1];

		res[i + iSeq[i]] = i + 1;
	}

	for (int i = 0; i < N; ++i)
		printf("%d ", res[i]);
}

• N번째는 가장 큰 수로, 가장 큰 수 인 자신보다 더 큰 수는 올 수 없으므로 inversion sequence의 마지막은 항상 0입니다. 이것을 활용하여 문제를 해결합니다.
• 마지막은 항상 0이기에 res[N-1]를 N으로 두고 시작합니다.
• N-2번째의 iSeq가 1이라면,  N-1번째에 있는 N은 N-2번째에 있는 값보다 앞에 있어야 합니다. 그렇기에 N-2번째에 있는 값을 왼쪽으로 이동시킵니다.
• 이러한 공식을 통해, 현재 선택된 i 값에서 iSeq[i]만큼을 왼쪽으로 이동시키며 자리를 찾아가는 방법으로 문제를 해결할 수 있습니다.