#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
int n, temp, x, count, cur;
scanf("%d", &n);
vector<int> is(n+1, 0);
vector<int> num(n+1, 0);
for(int i = 1; i < is.size(); i++)
{
scanf("%d", &is[i]);
num[i] = i;
}
count = 0;
x = n;
while(x != 0)
{
count = is[x];
cur = num[n];
for(int i = n; i >= 2; i--)
{
temp = num[i-1];
num[i-1] = num[i];
num[i] = temp;
}
for(int i = 1; count != 0; i++)
{
if(num[i] < num[i+1])
{
temp = num[i+1];
num[i+1] = num[i];
num[i] = temp;
count--;
}
}
x--;
}
for(int i = 1; i < num.size(); i++)
printf("%d ", num[i]);
return 0;
}1. 자연수 범위 n의 입력을 받고 자연수 범위이므로 이해하기 쉽게 vector의 크기를 n+1 만큼 지정해준다.
2. is는 inversion sequence 수열을 저장한 vector이고 num은 실제 수열의 vector이다.
3. 원리는 다음과 같다.
i) num 에서 맨 오른쪽 원소(가장 큰 숫자, 이하 타겟)를 맨 왼쪽으로 삽입정렬로 보낸다.
ii) 타겟을 오른쪽 원소와 비교해가면서 오른쪽 원소보다 작다면 남은 count에서 1을 빼고 오른쪽으로 이동한다.
iii) 만약 count가 0이라면 더이상 이동할 수 없다고 판단하고 x--를 한다.
x = 8
is[8] = 0(count)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
↓ i 단계 진행 ↓
| 0 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
count = 0 이므로
x--
x = 7
is[7] = 1(count)
| 0 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
↓ i 단계 진행 ↓
| 0 | 7 | 8 | 1 | 2 | 3 | 4 | 5 | 6 |
count = 1
↓ ii 단계 진행 ↓
| 0 | 8 | 7 | 1 | 2 | 3 | 4 | 5 | 6 |
count = 0 이므로
x--
이후 반복
걸린 시간 : 43분 33초
강의를 보고나서 다시 짠 코드
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
int n, temp, x, count, cur;
scanf("%d", &n);
vector<int> is(n+1, 0);
vector<int> num(n+1, 0);
for(int i = 1; i < is.size(); i++)
{
scanf("%d", &is[i]);
num[i] = i;
}
for(int i = n; i >= 1; i--)
{
count = is[i];
for(int j = i; j < i + count; j++)
{
temp = num[j+1];
num[j+1] = num[j];
num[j] = temp;
}
}
for(int i = 1; i < num.size(); i++)
printf("%d ", num[i]);
return 0;
}훨씬 간결한데, 그 이유는 다음과 같다.
- 맨 오른쪽 숫자부터 시작하는 것은 같다.
- is[x] 만큼 그 자리에서 삽입정렬로 높은 인덱스에 위치한 수와 바꾼다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
is[8] = 0이므로 삽입정렬 x
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
is[7] = 1이므로 인덱스가 1 높은 8과 바꾼다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 7 |
is[6] = 1이므로 인덱스가 1 높은 7과 바꾼다.
| 0 | 1 | 2 | 3 | 4 | 5 | 8 | 6 | 7 |
is[5] = 2이므로 인덱스가 1,2 높은 8,6과 바꾼다.
| 0 | 1 | 2 | 3 | 4 | 8 | 6 | 5 | 7 |
이후 반복
