365일 민스

주식가격이라니, 솔깃한 테마이다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

첫번째 시도

문제 자체는 쉽다. 

prices의 각 가격에 대해서 다음 가격부터 끝까지 검사하면 된다. 

아래와 같이 구현했는데... 

효율성테스트에서 떨어졌다. 

def solution(prices):
    # 1번째 요소는 2번째부터 처음부터 끝가지
    # 2번재 요소는 3번째부터 끝까지.... 
    # 즉 하나씩 빼면서 세기만하면됨 
    answer = [] 
    while prices:
        price = prices.pop(0)
        cnt = 0
        for elem in prices:
            if elem >= price:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)
    return answer

두번째시도

나를 믿지말고 라이브러리를 믿어라.

collections는 기본 라이브러리이기때문에 대부분의 코테에서 임포트 가능하다.

collections의 deque는 스택과 큐의 역할을 모두 수행할 수 있고, 이중연결리스트로 구현 되어 있다. 

때문에 큐나 스택같이 리스트의 왼쪽이나 오른쪽에 접근하는 경우 높은 효율성을 자랑한다. 

앞으로 큐/스택를 활용할 때에는 무조건 deque로 만들자.

from collections import deque
def solution(prices):
    prices=deque(prices)
    answer = [] 
    while prices:
        price = prices.popleft()
        cnt = 0
        for elem in prices:
            if elem >= price:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12909

[접근법]

기본적인 스택 문제라고 한다. 

기본적인 스택에서 문자열 검사할 때 이렇게 접근하면 좋을거같다. 

외워두자(코테가 참 무슨의민지).

1. 전체 문자열을 순회(O(N))

2. 매칭쌍중 하나를 지정해서 발견할때마다 스택에 쌓기 

3. pair를 이루는 문자열 발견시 스택에서 하나씩 빼기 

4. 마지막에 스택 검사해 길이가 0이 아니면 불완전 매칭 쌍 존재 --> False 리턴 

def solution(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append(c)
        elif len(stack) !=0 and c ==')':
            stack.pop()
        else:
            return False
    if len(stack) !=0:
        return False
    else:
        return True

탐색 문제를 풀기 위해서 먼저 스택과 큐에 대한 문제들에 익숙해지기로 했다. 

https://school.programmers.co.kr/learn/courses/30/lessons/12906

스택/큐로 분류된 문제인데, 사실 파이썬에서는 리스트로 다 처리할 수 있다. 

초기값을 할당하고 이전 저장 요소만 검사해 추가한다. 

복잡도는 N-1이 된다.