우주의 IT 소행성

파이썬의 pop() 함수를 잘 사용하여 풀 수 있음(deque 처럼, pop(0), pop())

+ 문제에 reverse 기능이 있는데, 이런 reverse가 나올 떄에는 2번 호출되면 제자리로 돌아온다는 사실을

항상 인지하고 있어야 한다. 매번 reverse를 해주면 그만큼 사용하는 메모리가 많아진다.

그리고 어차피 reverse를 하더라도 주어진 연산은 삭제밖에 없으니, reverse의 토큰 수에 따라서 왼쪽이나 오른쪽 수를 지워주기만 하면 된다.,

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    commands = input()
    n = int(input())
    data = input().rstrip()[1:-1].split(",")
    result = 0
    reverse_count = 0

    if n == 0:
        data = []

    for command in commands:
        if command == 'R':
            reverse_count += 1

        elif command == 'D':
            if len(data) > 0:
                if reverse_count % 2 == 0:
                    data.pop(0)
                else:
                    data.pop()
            else:
                result = -1

    if reverse_count % 2 == 1:
        data.reverse()
    if result == -1:
        print("error")
    else:
        print("[" + ",".join(data) +"]")

import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
token = [-1 for _ in range(n)]

for i in range(n):
    for j in range(i + 1, n):
        if data[i] < data[j]:
            token[i] = data[j]
            break

for ans in token:
    print(ans, end=' ')

1번째 시도 시간초과 코드

import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
token = [-1 for _ in range(n)]
stack = []

stack.append(0)
for i in range(1, n):
    while stack and data[stack[-1]] < data[i]:
        token[stack.pop()] = data[i]
    stack.append(i)
print(*token)

2번쨰 시도 정답 코드

1번쨰 시도에서 모든 데이터 N개를 N번 비교하여 오큰수를 구하였으므로 시간복잡도는 n의 제곱으로 상승하였다.

따라서 시간 초과가 발생하였다.

이를 해결하기 위해서는 조금 더 유연한 사소가 필요하다.

stack을 값이 아닌 인덱스 를 저장하는 매개체로 삼아 복잡도를 대폭 하락시켰다.

i번째 인덱스의 오큰수를 구할 때 마다 stack의 인덱스를 상승시켜 값을 넣어주고, 만약 오큰수를 찾지 못했다면 pass하여 -1로 남긴다.

시리즈에 맞게 역시 itertools의 combinations_With_Replacement (중복조합)을 이용하면 되는 문제

이 itertools에 관련된 총 정리글을 조만간 게시글에 올려봐야겠다.

from itertools import combinations_with_replacement
n, m = map(int, input().split())
data = [i for i in range(1, n + 1)]
for i in combinations_with_replacement(data, m):
    for j in i:
        print(j, end=' ')
    print()

이전번 문제와 동일하게 itertools의 product(중복순열)을 이용하였다.

특이하게 매개 값에 2 같은 정수형 자료가 들어가면 안되고

repeat = (int) x 로 반복 수를 넣어주어야 한다.

from itertools import product
n, m = map(int, input().split())
data = [i for i in range(1, n + 1)]
for i in product(data, repeat = m):
    for j in i:
        print(j, end=' ')
    print()