우주의 IT 소행성

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()

1부터 N까지 자연수 중 중복 없이 M개를 고른 수열의 집합

-> Combination (조합)

파이썬 라이브러리 itertools의 combinations을 이용하여 손쉽게 풀 수 있는 문제.

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