.PNG)
31. 역수열(그리디)
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 7
<내 풀이>
어떻게 풀이해야할지 감이 안 잡힌다
n=int(input())
a=list(map(int,input().split()))
k=[]
s=[0]*n
for i in range(1,n+1) :
k.append(i)
<풀이>
- [ 0 0 0 0 0 0 0 0 ]
0박스들이 갯수만큼 있다고 생각하고
자기 앞에 있는 자기보다 큰 숫자의 개수들 = 0의 개수다
먼저 1 은 자기 앞에 5개의 큰 숫자가 있으니 0 5개 뒤에 자리잡는다[00000100]
2는 3개 있으니깐 0 3개 뒤에[00020100]
3은 4개 있으니깐 0 4개 뒤에[00020130] .... 이런식으로
n=int(input())
a=list(map(int,input().split()))
s=[0]*n
for i in range(n) :
for j in range(n):
if a[i]==0 and s[j]==0:
s[j]=i+1
break
elif s[j]==0:
a[i]-=1 #a[i]는 요구되는 0의 개수, 0찾을때마다 하나씩 줄이기
for x in s:
print(x,end=' ')<다른 분들의 풀이> (1)
n = int(input())
a =list(map(int,input().split()))
a = a[::-1]
ans=[]
for x in a:
ans.insert(x,n)
n -=1
#print(ans)
# 리스트를 먼저 뒤집은 다음에 가장 큰수 부터 차례 차례로 해당 인덱스에 인서트 해줘도 되는 것=> N부터 처리한다는 것은 ans에 이미 들어가 있는 숫자는 현재 처리하려는 숫자보다 모두 크다는 것이므로
현재 처리하려는 숫자가 x번 index로 insert되면 자기 앞에 무조건 큰 숫자가 x개 생기고 _현재 숫자 다음에 처리되는 숫자들은 자기보다 작기때문에 어디에 insert 돼도 상관없습니다.
<다른 분들의 풀이> (2)
N = int(input())
a = list(map(int,input().split()))
ra = []
i = N
while i>0:
ra.insert(a[i-1],i)
i -= 1
for x in ra:
print(x,end=' ')=> 입력받은 역수열의 마지막 index 부터 접근하여 차례로 해당 index에 삽입
<반성점>
- 구현이 힘들다
- 사고력을 요하는 문제들을 유연하게 다가가지 못한다. 강사님의 사고를 암기하고 복습하면서 사고력을 높이고 문제를 바라보는 힘을 키우자
- 다른 분들의 풀이를 보면서도 생각을 보완하자
<배운 점>
-
list.index(element, start, end)
: element - the element to be searched
start (optional) - start searching from this index
end (optional) - search the element up to this index -
insert(a, b)는 리스트의 a번째 위치에 b를 삽입하는 함수
