[Inflearn] PS - 006

문제 출처 : inflearn <파이썬 알고리즘 문제풀이(코딩테스트 대비)>

역수열(그리디)

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞
에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다.
예를 들어 다음과 같은 수열의 경우
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의 역수열은 5 3 4 0 2 1 1 0 이 된다.
n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출
력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 역수열이 숫자 사이에 한
칸의 공백을 두고 주어진다.

▣ 출력설명
원래 수열을 출력합니다.

▣ 입력예제 1
8
5 3 4 0 2 1 1 0

▣ 출력예제 1
4 8 6 2 5 1 3

풀이

'''
시작 : 09:40
종료 : 10:10

접근
1. 1은 역수열의 인덱스 그대로 원래 수열에 넣어주면 된다.
2. 원래 수열의 첫번째 숫자는 반드시 역수열에서 0이다.
3. 원래 수열의 두번째 숫자는 1 또는 0을 갖는다.
4. 원래 수열의 세번째 숫자는 0~2의 숫자를 갖는다.

1. 1의 위치 정해지면 남은 위치는 그냥 찾을 수 있지 않나?

결과 : 시간 초과
이유
1. 방법은 생각해냈는데, 구현이 안된다.
    → greedy를 써서 어떻게 구현할지 감이 안잡힘.
        → 개념과 문제가 연결이 안됨. 
'''