[프로그래머스] 뒤에 있는 큰 수 찾기 (파이썬)

출처: 뒤에 있는 큰 수 찾기

---

문제

나의 답안

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    
    for idx, value in enumerate(numbers):
        while True:
            if not stack:
                break
            if numbers[stack[-1]] < value:
                pre = stack.pop()
                answer[pre] = value     
            else:
                break
        stack.append(idx)
    return answer

접근 방법

• 스택을 사용하여 이중루프를 제거하는 방식
  • LIFO라 이중루프를 사용할 필요가 없음, 새로운 숫자를 스택의 top과 비교
• 더 큰 수를 찾지 못하는 경우를 대비해 answer을 -1로 초기화한다.
• 현재 숫자(value)보다 작은 숫자들만 스택에 남아있고, 더 큰 숫자가 나올 때까지 기다리게 됨
• 현재 값(value)이 스택의 top 값보다 크면(numbers[stack[-1]]) => 더 큰 수를 찾은 것
  따라서, 해당 인덱스를 pop하고 answer에 해당 숫자를 업데이트 해준다.

실패 답안1

def solution(numbers):
    dic={}
    
    for idx, val in enumerate(numbers):
        dic[idx] = val

    for idx, val in dic.items():
        if idx == len(numbers) - 1:
            dic[idx] = -1
            continue
        for j in range(idx, len(numbers)):
            if val < dic[j]:
                dic[idx]=dic[j]
                break
            elif val > dic[j]:
                dic[idx]=-1
            
    return list(dic.values())

데이터와 인덱스값을 구분하기 위해 딕셔너리를 사용했다.
인덱스를 키 값으로 저장해서 값을 변경할 때 편리하게 변경하고 싶었다.
그러나 괜히 복잡하게 인덱스 값을 별도로 구별할 필요가 없는 문제라는 것을 알게됐다.

실패 답안2

def solution(numbers):
    answer = []
    tf = True
    for i in range(len(numbers)):
        tf = False
        for j in range(i+1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                tf = True
                break
        if tf != True:
            answer.append(-1)
    return answer

그래서 접근한 두번째 방법
단순 리스트로 bool 변수를 두어 더 큰수를 찾았는지를 체크하고, 더 큰수가 없으면 -1을 추가해주는 로직이다.
그러나 여전히 이중루프를 사용하게 되면서 n^2의 시간 복잡도를 가지게 된다.. 결과는 시간초과