230412 TIL 자잘한 코테 공부

나는 코린이니까 스택과 큐 한놈만 팬다.

 

프로그래머스 스택과 큐

기능개발 (lv.2)

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

프로그래머스

- 시간을 구하는 것까지는 쉬웠는데 그 다음이 어려웠다. -> 큐로 접근해야하는 문제

- 비슷한 문제를 반복해서 보니 유형을 알겠다.

 

유튜브 참고

기능 개발 문제 풀이: https://www.youtube.com/watch?v=rdiXbJzgBPQ 

import math
def solution(progresses, speeds):
    answer = []
    temp = []
    for i in range(len(progresses)):
        days = (100 - progresses[i]) / speeds[i]
        temp.append(math.ceil(days))
    
    while temp:
        out = temp.pop(0) #temp[0]이 out 보다 커지면 다시 여기로
        result = 1
        while len(temp) != 0 and out >= temp[0]: # 몇 번 반복할 지 몰라서 while
            #나온 값과 빠져나온 뒤의 첫번째 값과 크기 비교해서 나온 값이 더 크면
            result += 1 # 1을 더한다.
            temp.pop(0) # 그리고 그 값을 꺼낸다
        answer.append(result) #그리고 새로운 리스트에 값을 추가
    return answer
"""
[7, 3, 9] => [2,1]
[1 + 7보다 작으면 1 / 7보다 크면 새로 !1]
[5, 10, 1, 1, 20, 1] => [1,3,2]
[1 / 5보다 커서 !1 / 10보다 작아서 +1 +1 / 10보다 커서 !1 / 20보다 작아서 +1]
"""

 

큐를 활용하는 유사한 다른 문제: https://www.youtube.com/watch?v=YlIPiNnj0Js 

- while에 조건 2개 and로 연결

- 큐에서 꺼낼때는 연산이나 슬라이싱으로 꺼내는 것을 피하고 append와 pop을 써야 시간복잡도가 줄어든다.

 

 

스택 - 올바른 괄호

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

프로그래머스

참고영상: https://www.youtube.com/watch?v=yAYycu0nCCU&t=351s 

예전에 풀었던 문제인데, 다른 풀이방법을 참고해서 또 풀어봤다.

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

- 통과하긴 했지만, 효율성이 높지 않음;;

 

데큐(deque)

- 양방향 큐

- 프로그래머스 프린터 문제는 데큐로 풀면 잘 풀릴듯

from collections import deque
a = [10, 20, 30, 40, 50]
d = deque(a)
dir(d)
# popleft, rotate, appendleft

d.rotate(1) # 1칸씩 오른쪽으로 이동