[TIL_Carrotww] 21 - 22/09/28

📝Carrotww의 코딩 기록장

💡 Stack & queue Algorithm

🧲 오늘의 알고리즘 1

🔍주식가격 - 프로그래머스 Level2

• 첫 번째 풀이

def solution(prices):
    result = [0] * len(prices)
    temp = list(zip(prices, range(1, len(prices) + 1)))
    for te, nu in temp:
        for te2, nu2 in temp[nu:]:
            if te <= te2:
                result[nu - 1] += 1
            else:
                result[nu - 1] += 1
                break
    return result

• 두 번째 풀이

def solution(prices):
    result = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] <= prices[j]:
                result[i] += 1
            else:
                result[i] += 1
                break
    return result

• 세 번째 풀이

def solution(prices):
    length = len(prices)
    result = [x for x in range(length - 1, -1, -1)]
    stack = []
    for i in range(length):
        while stack and prices[i] < prices[stack[-1]]:
            temp = stack.pop()
            result[temp] = i - temp
        stack.append(i)
    return result

도무지 stack을 활용하여 풀 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였다.
result 를 역순으로 초기화 한 이유는 for 문안에서 예시의 index 0 자리에 있는 1 같은 경우는 리스트 안에서 1보다 작아지는 경우가 없어 숫자 갱신이 되지 못한다

result = [0] * len(prices)
#생략
while stack:
	temp = stack.pop()
    result[temp] = len(prices) - 1 - temp

위와 같은 식으로 마지막에 stack에 남아있는 부분들을 처리해줘도 되지만 처음부터 역순으로 초기화를 시킨다면 위와 같은 잔 처리 부분을 수행할 필요 없으므로 좋은 것 같다.

확실히 stack을 사용하여 실행을 하니 효율성 테스트에서 시간이 많이 단축되었다.

🧲 오늘의 알고리즘 2

🔍 프린터 - 프로그래머스 Level2

• 내 풀이 stack, queue 활용 (정답)

from collections import deque

def solution(priorities, location):
    stack = [[-1, -1]]
    temp = zip(priorities, range(len(priorities)))
    queue = deque(temp)
    while stack[-1][1] != location:
        value = queue.popleft()
        for pr, num in queue:
            if value[0] < pr:
                queue.append(value)
                break
        else:
            stack.append(value)

    return len(stack) - 1

1. temp list에 주어진 priorities 값과 해당 값의 location인 인덱스를 zip을 활용하여 같이 묶어 주어
2. while 문을 수행할때 stack 에 들어가있는 location 값이 문제에서 주어진 location과 같으면 while 문을 종료한다.
3. queue 왼쪽(앞부분) 에서 프린트 해도 되는지 value에 저장을 한 후
   queue 에 남아있는 값들과 비교를 하여 더 큰 값이 있다면 queue의 맨 뒤로 보낸 후 for 문을 종료한다.
4. for문에서 수행된 것이 없다면 else 문을 타 stack에 추가해준다 (프린트 된다)

• 풀이를 적으며 생각해봤는데 stack은 활용을 안했다...ㅋㅋ
  처음에 무작정 stack을 활용하여 풀어보자는 목적으로 list 변수 명을 stack으로 사용하였지만 풀고보니 stack은 아닌걸로...ㅎ
  deque를 활용한 풀이이다.
• 두 번째 풀이

from collections import deque

def solution(priorities, location):
    stack = []
    queue = deque([(x, y) for x, y in enumerate(priorities)])
    cnt = 0

    while 1:
        temp_num, temp_pr = queue.popleft()
        if any(temp_pr < x[1] for x in queue):
            queue.append((temp_num, temp_pr))
        else:
            cnt += 1
            if temp_num == location:
                return cnt

다른 사람의 풀이를 활용한 것인데 그 분은 deque를 사용하지 않고 일반 리스트에서 pop[0]을 하여 풀이를 하였다.
난 pop[0] 을 하게되면 시간 복잡도가 N이 되기때문에 deque를 사용하여 다시 자료형을 만들어 주었고
cnt 값을 준 것과 any() 를 사용한것이 나와 다른 점 이였다.
확실히 cnt를 주고 return을 바로 해주니 깔끔하기는 하다.

몇 개 더 풀어봐야겠다
오늘 끝!