1138번: 한 줄로 서기 (구현)

1138번: 한 줄로 서기

간단한 아이디어 문제.

 

큰 수부터 아래와 같이 표에 채워넣으면 쉽다. 

arr = [5 3 2 2 0 0] 이란 정보가 주어지면, 먼저 6을 추가한다. 

6

5를 추가한다. 

6

5

5보다 큰 수가 0개이어야 하므로 0번째 index에 5를 끼어넣자. 

5

6

4를 추가한다 

5

6

4

 

3을 추가한다. 

5

6

4

3

3보다 큰 수가 2개 이어야 하므로 2번째 index 뒤에 끼워넣자. 

5

6

3

4

 

2를 추가한다. 

5

6

3

4

2

2보다 큰 수가 3개이어야 하므로 3번째 index 에 끼워넣자. 

5

6

3

2

4

 1을 추가한다. 

5

6

3

2

4

1

1보다 큰 수가 5개이어야 하므로 5번째 index에 끼워넣자. 

끼어넣기는 삽입정렬과 동일하게 두 자리의 위치를 계속 바꿔가며 내려가는 순으로 진행한다.

다만 조건을 현재 위치에서 왼쪽에 있는 수 중 자신보다 큰 수의 개수와 문제에서 준 것과 같은지 확인한다. 

 

n = int(input())
arr = list(map(int,input().split()))
ans = []
# 현재 index보다 작은 인덱스 중에서 키가 큰 사람의 수를 구한다.
def cnt_tall(arr,index):
    cnt = 0
    for i in range(index):
        if arr[i] > arr[index]:
            cnt += 1
    return cnt
 
# n번 추가하고 끼어넣자
for i in range(n):
    ans.append(n-i) 
    for j in range(i,0,-1): 
        if cnt_tall(ans,j) == arr[n-i-1]:
            break
        ans[j],ans[j-1] = ans[j-1],ans[j]
for i in ans:
    print(i, end= ' ')