[Programmers/Level 2] 탑

https://programmers.co.kr/learn/courses/30/lessons/42588

def solution(heights):
    answer = [0] * len(heights)
    
    for i in range(len(heights)-1, -1, -1):
        for j in range(i-1, -1, -1):
            if(heights[i]<heights[j]):
                answer[i] = j+1
                break
    return answer

정확성 테스트

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.6MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.6MB)
테스트 7 〉	통과 (0.04ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

근데 이거 시간복잡도 최악,,,

 

---

다른 분 코드

def solution(heights):
    stack = []
    stack.append(0)
    max_pos = 1
    max_val = heights[0]

    for i in range(1,len(heights)):
        if heights[i] >= max_val:
            stack.append(0)
            max_pos = i+1
            max_val = heights[i]
        if heights[i] < max_val:
            stack.append(max_pos)
        if heights[i] < heights[i-1]:
            max_pos = i
            max_val = heights[i-1]
            stack.pop()
            stack.append(max_pos)

    return stack

이렇게 푸는게 맞는것같다..고 생각했는데 댓글보고 해보니까 테스트는 통과해도 [10, 8, 6, 9]는 통과 못한다

일단 저렇게 생각하는거 알아두는걸로!