https://www.acmicpc.net/problem/1138
initial
This question is very hard to think of the implementation. I first thought of placing people with values 0 (no one to his left) to the front but this is not always the case because you can have people with value 0 in the middle of the queue if he is very tall.
I also tried topological sort but we have no info regarding a->b and whether it is a DAG so nope.
So googled the solution. As we iterate through the person number, we initialise count variable as 0, which represents total number of peeps to his left. Then we iterate through the index of answer list, where this person is gonna be placed and we will be incrementing count. When count is equal to lst[i], which means number of peeps to his left matches the criteria, and when ans[j] is 0, which means there is no one placed at that index, then we place this person in that index and break. Impt to break cuz else it will continue to next j and this person might be placed in multiple indexes in our list.
So something like this
0 0 1 0 // 왼쪽에 두명이 있으므로 2칸을 비워두고 자리를 채운다.
0 2 1 0
0 2 1 3
4 2 1 3
This kind of greedy impl is hard to think of so needs practice.
revisited may 31st
I think the most impt assumption as to how and why this solutions works is iterating from person number lowest to highest. We know that when we place a short person and start up, the next taller people will not have to account for this short person (cuz the given list only takes into account taller people to oneself, not shorter people). So by leaving space for taller people and incrementing count, and only placing that person when count (i.e. taller people to oneself) is equal to given_lst[iter_j], this is clever.
solution
n = int(input())
lst = list(map(int, input().split()))
ans = [0 for _ in range(n)]
# i is person number
for i in range(n):
count = 0
# j is index where this person is to be placed in this ans list
for j in range(n):
if count == lst[i] and ans[j] == 0:
ans[j] = i + 1
break # Break the loop once the person is placed
elif ans[j] == 0:
count += 1
print(*ans)complexity
n^2 time and n space? yes
The time complexity of the provided code is O(n^2), where n is the number of people. This is because there are nested loops: one loop to iterate through each person (n iterations), and another loop to find the position to place each person in the output list (potentially n iterations).
The space complexity is O(n) because the code uses a list (ans) of size n to store the final positions of the people in the line.
