먼저 역수열을 원래수열로 만들어봐야 한다


예제처럼 숫자의 개수가 8일때

5 3 4 0 2 1 1 0 를 원래 수열로 만들어 보면


먼저 1부터 N까지의 수를

한번씩만 사용해서 이루어진 수열이고

앞에 자기보다 큰수가 있으니까

1~8을 오름차순으로 나열해서 풀어야 한다


역수열

5 3 4 0 2 1 1 0


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1 2 3 4 5 6 7 8


X X X X X X X X

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


1은 자신보다 큰 값이 다섯개 있다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1 2 3 4 5 6 7 8


X X X X 1 X X X

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


2는 자신보다 큰 값이 세개 있다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1 2 3 4 5 6 7 8


X X X 2 X 1 X X

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


3은 자신보다 큰 값이 네개 있다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1 2 3 4 5 6 7 8


X X X 2 X 1 3 X

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


...


자신보다 작은 숫자는 상관없고

큰숫자들이 들어오니까 X의 개수만큼


인덱스0~7을 숫자 1~8이라고 생각하고

a[i]에는 자신이 몇번째인지가 들어있으니까


i를 1씩 감소시키다가 0이 됐을때

j에 값이 없는지 확인하고 넣으면 된다



자신의 자리를 찾는 i와 빈공간을 찾는 j

두가지 포문안에서


i가 자신의 자리를 찾았을때 0이 되므로

seq[j]가 0인경우 원래값인 i+1을 넣고


a[i]는 0이 아닌데 seq[j]가 0인경우

a[i]를 1 감소시킨다



꿈★은 이루어진다

내일채움공제 되는 중소기업 가자 화이팅!