문제
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 <stdio.h>
#include <vector>
using namespace std;
int main () {
int n, i, j, pos;
scanf("%d", &n);
vector<int> is(n + 1);
vector<int> os(n + 1);
for(i = 1; i <= n; i++) {
scanf("%d", &is[i]);
}
for(i = n; i >= 1; i--) {
pos = is[i];
if(pos == 0) {
os[i] = i;
} else if(pos > 0) {
for(j = i; j < i + pos; j++) {
os[j] = os[j + 1];
}
os[i + pos] = i;
}
}
for(i = 1; i <= n; i++) {
printf("%d ", os[i]);
}
return 0;
}
설명
사용자로부터 입력받은 수열을 is배열에 할당한다.
is배열을 거꾸로 순회하여 해당 값이 할당받은 os배열에서 is배열의 값 만큼 앞으로 복사하고 그 다음 index에 해당 값이 할당되도록한다.
따라서 pos를 is배열의 값으로 할당하고 해당 pos가 0이면 앞에 큰 수가 없다는 것을 의미하므로 os배열에 해당 index(1부터 시작하는 값)를 할당한다.
만약 pos가 0보다 크다는 것은 앞에 큰 수가 있다는 것을 의미하므로 j가 현재 is배열의 index를 기점으로 pos만큼 반복하는 for문을 작성하여 os배열에 있는 값들을 pos만큼 앞으로 복사한다.
이후 마지막 위치에 현재 is배열의 index값을 할당하면서 반복한다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
