Как ускорить программу? Есть решение, но 5 тестов из 10 не проходят по времени (3 секунды)

Question

Нумерация Власти города Байтленда решили построить новый микрорайон, который будет состоять из одной длинной улицы. Процесс постройки домов будет выглядеть следующим образом. Сначала будет построен самый первый дом, который получит номер 0. (Разумеется, в Байтленде все нумерации начинаются с нуля.) Далее все дома будут пристраиваться слева или справа от существующей застройки. Дома будут получать номера в порядке их ввода в эксплуатацию.

Рассмотрим пример. Пусть, дом номер 1 был построен слева от дома номер 0. Тогда нумерация домов слева направо будет выглядеть как 1 0. Далее был построен дом номер 2 слева от существующих. Теперь дома на улице будут иметь номера 2 1 0. Далее был построен дом номер 3 справа от существующих. Теперь на улице будут стоять дома с номерами 2 1 0 3. Наконец, если дом номер 4 будет построен слева, а дома с номерами 5 и 6 справа, то последовательность номеров домов превратится в 4 2 1 0 3 5 6.

На улице построили n домов с номерами от 0 до n-1. Для каждого дома с ненулевым номером нам стало известно с какой стороны от существующих он был построен. Теперь ваша задача — написать программу, которая перечислит номера домов в порядке движения по улице слева направо.

Формат входных данных В первой строке на вход подается число n — количество построенных домов. 2 ≤ n ≤ 400000. Во второй строке записана последовательность из n−1 символов "L" или "R" (без кавычек). Символ "L" в i-той позиции означает, что дом с номером i был построен слева от предыдущих, а символ "R" — справа.

Формат выходных данных Вывести через пробел в одной строке последовательность из n чисел — нумерацию домов после завершения строительства.

Методика проверки и описание тестов Программа проверяется на 10 тестах. Прохождение каждого теста оценивается в 2 балла. Тест из условия задачи при проверке не используется.

В первых пяти тестах n ≤ 100.

Sample Input:
7
LLRLRR

Sample Output:
4 2 1 0 3 5 6

Мое решение:

dom = int(input())
a = input()
spisok = [0]
k = 0
while k < dom - 1:
    if a[k] == 'L':
        spisok.insert(0, k + 1)
    if a[k] == 'R':
        spisok.append(k + 1)
    k += 1
print(*spisok)

Answer 1

Складывайте левые и правые дома в отдельные списки аппендом.

Потом переверните левый список, выведите его, потом правый.

(инсерт в начало списка вызывает постоянные перераспределения памяти)

dom = int(input())
a = input()
spisokL = []
spisokR = [0]
k = 0
while k < dom - 1:
    if a[k] == 'L':
        spisokL.append(k + 1)
    if a[k] == 'R':
        spisokR.append(k + 1)
    k += 1
spisokL.reverse()
print(*spisokL, *spisokR)

Answer 2

можно вот так:

left = []
right = []
index = 1
for dir in data:
    if dir == 'L':
        left.append(index)
    else:
        right.append(index)
    index += 1

spisok = left[::-1] + [0] + right

или так:

left = []
right = []
for dir in enumerate(data, 1):
    if dir[1] == 'L':
        left.append(dir[0])
    else:
        right.append(dir[0])

кстати, задача может быть решена в 1 строчку, но решение чуть медленнее приведённых выше

spisok = list(map(lambda key: key[0], filter(lambda obj: obj[1] == 'L', enumerate(data, 1))))[::-1] + [0] + list(map(lambda key: key[0], filter(lambda obj: obj[1] == 'R', enumerate(data, 1))))

или так:

spisok = [obj[0] for obj in enumerate(data, 1) if obj[1] == 'L'][::-1] + [0] + [obj[0] for obj in enumerate(data, 1) if obj[1] == 'R']

БЛОГ НА HUSL

Как ускорить программу? Есть решение, но 5 тестов из 10 не проходят по времени (3 секунды)

Ответы (2 шт):