Inversion Sequence / c / 제한시간 없음

▣ 문제

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

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, j;
	int temp;
	int cnt = 0;
	int num[101] = { 0 };
	int pos = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &temp);
		cnt = 0;
		pos = 0;
		for (j = 1; j <= n; j++) {
			if (num[j] == 0) {
				cnt++;
			}
			if (cnt == temp) {
				pos = j;
				break;
			}
		}
		if (num[pos + 1] == 0) num[pos + 1] = i;
		else {
			for (j = pos + 1; j <= n; j++) {
				if (num[j] == 0) {
					num[j] = i;
					break;
				}
			}
		}
	}



	for (int i = 1; i <= n; i++)
		printf("%d ", num[i]);

	return 0;
}

내가 문제를 풀때는 접근 방법은 다음과 같다. 만약 다음과 같은 수열이 입력되었으면

8
5 3 4 0 2 1 1 0

 

num[101] 배열을 모두 0으로 초기화 시켜준 후 for문을 이용해 0값일때마다 cnt++를 해주었다.

 

그리고 cnt와 입력된 temp(inversion sequence의 값)이 일치하면 바로 다음 배열에 i 값을 저장했다.

 

만약 다음 배열값이 이미 다른 숫자가 들어가있다, 그 다음 빈 배열에 값을 저장했다.

0	0	0	0	0	0	0	0
cnt++	cnt++	cnt++	cnt++	cnt++	1

<inversion sequence의 1 이 5일때>

0	0	0	0	0	1	0	0
cnt++	cnt++	cnt++	2

 

<inversion sequence의 2 이 3일때>

0	0	0	2	0	1	0	0
cnt++	cnt++	cnt++		cnt++		3

<inversion sequence의 3 이 4일때>

...

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, i, j;
	int pos;
	int is[101], os[101];
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &is[i]);
	}

	for (i = n; i >= 1; i--) {
		pos = i;
		for (j = 1; j <= is[i]; j++) {
			os[pos] = os[pos + 1];
			pos++;
		}
		os[pos] = i;
	}

	for (i = 1; i <= n; i++)
		printf("%d ", os[i]);

	return 0;
}

is 는 inversion sequence, os는 original sequence를 나타낸다.

 

이 코드의 접근 방법은 다음과 같다. 위의 수열을 그대로 사용한다면

8
5 3 4 0 2 1 1 0 <is>

1 2 3 4 5 6 7 8 <is값의 원래의 수>

 

8은 가장 큰 수이기 때문에 os의 가장 뒤에 넣는다.

1	2	3	4	5	6	7	8 ,start!
							8

7은 1개의 더 큰 숫자가 자기 앞에 있기 때문에, pos를 기준으로 1개를 자신 앞으로 땡기고 다음 배열에 자신(7)이 들어간다.

1	2	3	4	5	6	7, pos!	8
						8	7

6은 1개의 더 큰 숫자가 자기 앞에 있다. pos를 기준으로 1개를 자신 앞으로 땡기고 다음 배열에 자신(6)이 들어간다.

1	2	3	4	5	6, pos!	7	8
					8	6	7

5도 같은 방법으로 적용하면

1	2	3	4	5, pos!	6	7	8
				8	6	5	7

이와 같은 방법을 1까지 반복한다.

 

이 중 핵심 코드는 

for (j = 1; j <= is[i]; j++) {
os[pos] = os[pos + 1];
pos++;
}

앞으로 몇개만큼 땡겨주는지

 

.