뒤에 있는 큰 수 찾기
문제 설명
제한사항
입출력 예 및 설명
문제 풀이1
def solution(numbers):
answer = []
for i, n in enumerate(numbers):
index = 1
check = True
if (i == len(numbers)-1):
answer.append(-1)
break
else:
while check:
if i+index == len(numbers):
answer.append(-1)
break
if numbers[i] < numbers[i+index]:
answer.append(numbers[i+index])
check = False
else:
index += 1
return answer채점결과1
제한사항에서 numbers의 길이가 1,000,000 이하라고 했으니까 최악의 경우를 생각해보면 numbers의 길이가 1,000,000개라는 건데, 여기서는 시간 복잡도가 어떻게 되는 걸까??
그럼 어떻게 짜야할까.. 고민해보자.
문제 풀이2
def solution(numbers):
answer = []
i = 0
index = 1
while True:
if len(numbers) == 0:
break
if index == len(numbers):
answer.append(-1)
numbers.pop(0)
index = 1
else:
if numbers[i] < numbers[index]:
answer.append(numbers[index])
numbers.pop(0)
index = 1
else:
index += 1
return answerfor문을 안 쓰려고 while 하나만 사용해서 다시 짜봤다.
채점결과2
근데 결과가 더 안 좋네 ㅎ;
뒤에 있는 수랑 비교하는 부분을 다른 방식으로 짜야하는 건가? numbers의 길이가 길어서 하나씩 비교하는 건 시간이 오래걸릴 것 같긴 하다. 그럼 어떻게 판단하지..?
다른 사람 풀이
def solution(numbers):
stack = []
result = [-1] * len(numbers)
for i in range(len(numbers)):
while stack and numbers[stack[-1]] < numbers[i]:
result[stack.pop()] = numbers[i]
stack.append(i)
return result
stack 자료형으로 풀이했다. 근데 나도 pop(0) 했는데, 이건 stack자료형은 아니지만 그래도 걸리는 시간은 똑같지 않나..?
검색해보니까, pop()은 O(1)인데 pop(0)은 O(n)이라고 한다. (아래 추가 설명)
a.pop(0)
리스트의 첫번째 값을 출력해 주는 연산입니다. 맨뒤에 값을 빼내는 pop는 복잡도가 O(1)인데 이것은 O(N)인 이유는 맨앞에 있는 값을 출력 해주기 위해 전체 복사를 해주기 위해서 입니다. (근데 맨 앞에 있는 값을 출력해주는 거랑 전체 복사하는 거랑 무슨 관계..? -> 아 혹시, pop은 단순 출력이 아니라 삭제 및 출력이라서 삭제가 된 list를 위해서 전체 복사를 한다는 말인가..?)
따라서 리스트 말고 deque를 이용하면 O(1)이 나옵니다. 백준에서 이 문제도 pop이 아닌 deque로 해결해야 시간초과 오류가 나지 않습니다.
출처: https://hyun-am-coding.tistory.com/entry/Python-list-연산에-따른-시간-복잡도 [현암 코딩:티스토리]
다른 사람 풀이 채점 결과
계속 Lv.1 만 풀다가 오늘 Lv.2 문제를 풀어봤는데, 쉽지 않다 ㅇㅅㅇ
그래도 하다보면 나도 쉽게 푸는 날이 오겠지!
파이팅 :)
문제 출처 : 프로그래머스