강의로 돌아가기
kimminha1994@gmail.com

이중 for문+break조합이랑 stack활용한 조합이 시간복잡도에서 어떤차이가 있나요?

for i, ele in enumerate(A):
for n in A[i+1:]:
if ele break
이런식으로 코드가 있다고 할때 break문때문에 시간복잡도는 줄 것이라 생각했는데
stack에서 index저장해서 진행하는거랑 복잡도가 어떻게 다른가요.?
stack으로 활용한 문제가 아직 어떤부분에서 이점으로 작용되는지 이해가 안되네요 ㅠ

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(numbers):
    answer = []
    stack = []
    answer = [-1 for i in range(len(numbers))]
    for i, ele in enumerate(numbers):
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        stack.append(i)
        # answer.append(-1)

#         checklist = ([num>ele for num in numbers[i+1:]])
#         if sum(checklist) == 0:
#             continue

#         for n in numbers[i+1:]:
#             if n>ele:
#                 answer[-1] = n
#                 break
    return answer
1 개의 답변
izjoker

예를들면, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,999] 같은 입력이 있다고 하면요.
2중 for문을 사용한 솔루션은 인풋에 따라 계산량이 줄 가능성이 있지만, 뒷큰수가 인풋의 맨 뒤에만 있는경우에는 break가 작동하지 않아서 의미가 없습니다.
이 경우 계산량은 n*logn 이 되겠죠.
반면 스택을 사용하는 경우 999에 도착할때까지 비교와 스택입력만 하게되므로 계산량 n, 마지막 항목에서 스택에서 쌓아둔 값을 하나씩 빼서 비교하는데 n이 들겠죠.
따라서 2n이 계산량이 됩니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.