210519 스택/큐 - 주식가격 문제 1트 실패

내가 알게만 간단정리

1. 스택 

LIFO

push : 스택의 마지막에 값을 넣는다. - list.append()

peek : 스택의 마지막에 있는 값을 확인 - list[-1]

pop : 스택의 마지막에 있는 값 추출(리턴 후 제거) - list.pop()

 

2. 큐

FIFO

put : 큐에 값을 넣는다 - list.append()

peek : 큐에 가장 앞에 남아있는 값을 확인 - list[0]

get : 큐에 가장 앞에 있는 값 추출(리턴 후 제거) - list.pop(0)

 

스택/큐로 풀어보는 프로그래머스의 주식가격 문제

결과적으로는 풀지 못해서 재도전을 할 것이고 검색으로 풀이법을 대충봐서 차이점을 일단 적어본다.

가장 큰 차이점은 answer 리스트의 길이를 미리 설정하냐 안하냐의 차이였다. 

나는 앞에서부터 append로 넣으려고 해서 index를 고민을 많이했었다.

 

============================================================================

# case 1

def solution(prices):
    answer = []

    for i, i_val in enumerate(prices):  # prices의 i번째 값과 i+1부터 마지막까지 비교하는 방식
        for j, j_val in enumerate(prices[i + 1:]):
            if i_val > j_val:
                answer.append(j + 1)  # i_val가 j_val이 커질 때 가격이 떨어진 판정을 내리고 그 때의 index차이를 append
                break
        else:
            answer.append(len(prices) - 1 - i)  # 위에 해당하는 경우가 없어 끝까지 온 경우의 index값 계산

    return answer

이 방법은 일단 정확성은 다 맞췄는데 속도에서 타임아웃이 나왔다. 

정답과의 비교로는 for문을 range로 돌렸다는 것과 answer의 길이를 미리 늘려놔서 append를 사용하지 않는다는 점.

 

============================================================================

# case 2

stack을 사용할 때 index를 어떻게 할 것인가를 해결하기 위해 나름대로 구현한 코드.

stack에 index와 값을 tuple로 넣는 형태로 구현해봤다. 

위에 일단 정답은 나오는 코드로 테스트 케이스를 많이 만들어서 돌려보고 같은 결과가 나왔는데

프로그래머스에서는 1번만 맞고 다 틀리게 나왔다. 왜 틀렸는지 궁금하다.

제한사항이나 리스트의 길이 같은게 걸리는게 아닐까 생각한다.

 

def solution(prices):
    answer = []
    stack = [[0, prices[0]]]  # 첫 값을 for문 안에 if로 넣으면 매번 해야되서 처음에 넣어줌
    result = []

    for idx, val in enumerate(prices[1:]):
        # idx + 1이 기본
        if stack[-1][1] > val:  # 스택의 마지막 값과 현재 값을 비교해서 마지막 값이 더 크면 가격이 떨어진 판정을 내림
            temp = stack[-1][1]

            for j in range(len(stack)):  # 스택에서 index값과 가격이 떨어지지 않은 기간을 계산해 임시 보관
                if temp == stack[-1][1]:
                    result.append([stack[-1][0], idx + 1 - stack.pop()[0]])
                else:
                    break
        stack.append([idx + 1, val])  # 스택의 마지막 값과 현재 값을 비교해서 마지막 값이 더 크지 않은 경우 스택에 저장

    for i in stack:  # 끝까지 가격이 떨어지지 않아 스택에 남은 값들의 index값과 가격이 떨어지지 않은 기간을 계산해 임시 보관
        result.append([i[0], len(prices) - 1 - i[0]])

    result.sort()  # index순으로 정렬

    for i in result:
        answer.append(i[1])  # 가격이 떨어지지 않은 기간만 append


    return answer

 

이것도 answer의 길이를 처음부터 늘려놨으면 해당 index의 값만 수정하면 되서 tuple로 고민할 필요가 없다.

다음에 재도전 해볼계획