스택

스택은 선형 리스트 중 하나다.

스택의 동작 원리

스택 문제

문제 1

올바른 괄호

틀린 풀이

def solution(s):
	stack = []
	if s[0] == ")" or s[-1] == "(":
			return False
	else:
		for c in s: 
			if not stack: # 비어있는 경우 
				stack.append(c) # 문제되는 로직
			else: 
				if stack[-1] == c:
					stack.append(c)
				else:
					stack.pop() 
					
	return False if stact else True

틀린 이유 : 스택이 비어있을 때 "(" 들어오면 안되는데, (바로 false 해야 함) 판단 없이 다 들어옴.

정답 풀이

def solution(s):
    stack = []
    for c in s:
        if c == "(":
            stack.append(c)
        elif c == ")":
            if not stack: 
                return False
            else: 
                stack.pop()
    return not stack

수정 부분 : 문자 자체를 기준으로 비교하는 방식으로 수정하였다. 이 풀이로 위의 스택이 비었을 때 "("이 들어오는 경우를 거를 수 있게 되었다.

문제 2

기능개발

틀린풀이

import math

def solution(progresses, speeds):
    result = []
    myList = [math.ceil((100-x)/y) for x, y in zip(progresses, speeds)]
    stack = []
    for i in myList: 
        if not stack:
            stack.append(i)
        else:
            if stack[-1] >= i:
                stack.append(i)
            else:
                result.append(len(stack))
                stack.clear()
                stack.append(i)
    if stack:
        result.append(len(stack))
    return result

틀린 이유 : 문제에서 구하라 바(return 값)를 잘못 이해했다. 위 풀이는 스택 안의 값과 들어오려는 값을 비교할 때 스택의 가장 마지막 요소만 비교하게 된다. 문제를 다시한번 해석해보면 이 로직으로는 문제에서 원하는 값을 도출해낼 수 없다.

정답 풀이

다음과 같이 그림을 그려서 문제를 정확히 이해해본 결과 스택의 가장 마지막 값과의 비교가 아닌 스택 내의 가장 큰 값과 비교해야 했다.

import math

def solution(progresses, speeds):
    result = []
    myList = [math.ceil((100-x)/y) for x, y in zip(progresses, speeds)]
    stack = []
    
    for i in myList:
        if stack and i > max(stack):
            result.append(len(stack))
            stack.clear()

        stack.append(i)
    result.append(len(stack))
    
    return result

파이썬 문법 정리

해당 문제에서 사용된 파이썬 문법은 다음과 같다. 나중에 사용될 수 있으니 기억해두자.

• 올림
  - math.ceil(x)은 x보다 크거나 같은 최소 정수를 반환 (import math 해서 사용)

• 길이가 같은 리스트 매핑
  1. zip (컴프리핸션)
  - [x + y for x, y in zip(a, b)]
  2. map + lambda
  - result = list(map(lambda x, y: x + y, list1, list2))

• 리스트 내부의 모든 요소를 삭제 clear()

큐

큐 문제

문제 1

프로세스

풀이

from collections import deque

def solution(priorities, location):
    dq = deque([(idx,p) for idx, p in enumerate(priorities)])
    p_dq = deque(priorities)
    result=[]
    
    while len(dq)>0:
        if dq[0][1] < max(p_dq): 
            dq.append(dq.popleft()) 
            p_dq.append(p_dq.popleft())
        else:
            result.append(dq.popleft())
            p_dq.popleft()
            
    for i in range(len(result)): 
        if result[i][0] == location:
            return i+1

• 문제 해석 : 큐와 프로세스 실행의 우선순위라는 단어가 나와 우선순위 큐를 구현하는 정렬 문제라고 생각했다. 그렇기에 sorted()를 사용하여 풀까 했지만 타겟값인 location은 priorities의 순서를 말하고 있기에 priorities의 값으로 비교하면 안되고 인덱스를 고려해야 하므로 sorted를 사용하지 않고 max를 사용했다.

• 정답은 맞췄지만 리스트를 3개나 생성했을 필요가 있을까 하는 생각이 든다. 다른 사람의 풀이를 보니 max를 사용하지 않았다. p_dq를 사용하지않고 dq만 사용하고 max를 이용하지 않고 문제를 해결하는 또다른 풀이를 생각해봐야겠다.

컬렉션 모듈

컬렉션 모듈에 대한 포스트

from collections import deque

• collections 모듈의 deque 클래스를 사용하겠다는 의미
• collections 모듈이 제공하는 자료구조
  

덱큐

• 양쪽 끝에서 삽입 및 삭제가 가능하다

from collections import deque

myList = [1, 2, 3]
dq = deque([1, 2, 3])

dq.append(4)         # 오른쪽 추가
dq.appendleft(0)     # 왼쪽 추가
dq.pop()             # 오른쪽 제거
dq.popleft()         # 왼쪽 제거

print(dq)  # deque([1, 2])