chp6 스택(Stack), chp7 큐(Queue)

이 글은 골든래빗 <코딩 테스트 합격자되기 파이썬편>의 6장, 7장 써머리입니다.

 

[스택 기본 개념]

선입후출 (FILO := First in Last Out) 형 자료구조.

먼저 쌓이면 나중에 나오는 자료구조.

제일 나중에 쌓인 것이 꺼낼 때 가장 먼저 나오는 구조이다.

삽입:= push,   꺼내기 := pop  

 

[큐 기본 개념]

선입선출 (FIFO)

원형 큐가 좀 더 효율적이지만 구현하기 복잡함. 코딩테스트에서는 이정도까지 고려할 필요 X

 

[스택 실전 문법]

python에서는 list의 append(), pop(), len()으로 삽입, 꺼내기, 크기 측정을 한다.

실전에선 이게 스택을 쓰는것인지 알기 쉽지 않으므로 스택을 사용하는 감을 익히는데 초점을 맞추자.

보통 불필요한 연산을 줄일려면..? 에서 스택이 하나의 대안이 될 수 있다.

 

[큐 실전 문법]

일반 list에서 append(), pop(0)을 사용한다. pop(0)은 선입선출 구현을 위한 것.

그러나 실제로는 deque(Double Ended Queue)를 많이 사용한다.

from collections import deque
queue = deque() # 정의
queue.append(1) # 추가
queue.append((x, y)) # 또는 queue.append([x,y]) 등 넣는 방법은 다양
해당변수 = queue.popleft()  # 선출하기. pop보다 매우 효율적!

 

 

 

 

---

Chp6 스택

 

 

 

문제 8) 괄호 짝맞추기

괄호가 ( )로 제대로 닫혀있으면 True, 아니면 False를 판별하는 함수를 완성하세요

#소괄호가 정상적으로 열고 닫혔는지 판별하는 함수 만들기
#idea: 가장 가까운.. 이라는 개념에서 스택 떠올리기
#하나의 통에 괄호 하나씩 입력하다가 닫는 괄호 나오면 같이 pop
def solution1(s):
    st = [] # stack을 담는 통
    for i in s:
        if i == '(':
            st.append(i)
        elif i == ')':
            if not st: # )가 나왔는데 기존이 비어있으면
                return False # early return
            else:
                st.pop() # )을 굳이 안넣고 기존 (만 pop
    if st: # 길이가 0이 아니면
        return False
    else:  # 길이가 0이면
        return True

s1 = '(())()' # Ture
s2 = '((())()' # False
s3 = ')(' # False
print(solution1(s1))
print(solution1(s2))
print(solution1(s3))

True
False
False

 

스택개념을 말 그대로 활용해본 기본 문제이다.

 

 

 

 

 

문제 9) 10진수를 2진수로 변환하기

10진수를 2진수로 변환하는 함수를 구현하세요.

# 파이썬 내장 이진법 함수를 이용한 것
def solution1(decimal):
    return bin(decimal)[2:]

내장함수를 이용하면 한 줄만에 끝난다. bin()은 문자열을 출력하며, bin()출력값 앞의 2글자가 몇진수인지 표시하는 문자가 나오므로 [2:]로 슬라이싱을 해주었다.

 

 

책의 풀이

def solution(decimal): #책의 풀이
    stack = [] #스택통
    while decimal > 0:
        remainder = decimal % 2
        stack.append(str(remainder)) #2로 나눈 나머지 push
        decimal //= 2 #계속해서 몫을 decimal로 정의
    stack.reverse() #거꾸로 읽어야하므로 뒤집는다.
    return ''.join(stack) #문자열로 출력
#이 경우 pop으로 하나하나 문자열을 더하기보다는
#join이 pop보다 시간복잡도가 효율적이므로 join을 사용한다

 

 

 

 

 

문제 10) 괄호 회전하기 

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

프로그래머스

# s를 왼쪽으로 전체길이 다 회전시킬때, 바른 괄호문자열의 개수가 result
# 이 문제는 ({[)]} 같은 경우는 0으로 정의한다. 즉, 여닫는 순서가 무조건 대칭이여야한다.
def is_vaild(s):
    stack = []
    # 괄호 짝을 dict로 정의
    brackets = {'(': ')', '[': ']', '{': '}'}
    for k in s:
        if k in brackets:  # key명시안안해도 자동 key값 체크
            stack.append(k)
        else:  # 굳이 따로 value로 안해도 나머지임
# stack이 비었거나 brackets[key]에 해당하는 value가 닫힌 k와 불일치하는 경우
            if not stack or brackets[stack.pop()] != k: #여기서 k는 닫힌괄호
                return False
    return not stack  # 빈 stack = True


def solution(s):
    answer = 0

    for i in range(len(s)):  # 문자열 움직이기
        rotated_s = s[i:] + s[:i] # 슬라이싱으로 rotate 구현!
        if is_vaild(rotated_s):
            answer += 1

    return answer

 

배운 아이디어:

1. stack 짝을 dict로 정의해서 key값과 value값으로 코드 작성 간편화

2. not stack = 빈 stack = True

3. rotate개념을 for문의 슬라이싱으로 구현하기.

 

 

 

 

 

 

 

 

 

문제 11) 짝지어 제거하기 

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

프로그래머스

def solution(s):
    lst = list(s)
    i = 0
    while i < len(lst) - 1:  # for문 대신 사용한 것
        if lst[i] == lst[i+1]:
            lst.pop(i) # pop을 해버리면
            lst.pop(i) # 하나가 없어지니 또 pop해야 함
            i = max(0, i-1) # i값이 음수 안되도록 조정
        else:
            i += 1
    if lst:
        return 0
    else:
        return 1

정확도는 통과하였으나 효율성테스트 0점(시간초과)인 코드이다.

 

def solution(s):
    i = 0
    while i < len(s) - 1:
        if s[i] == s[i+1]:
# 같은 문자일 경우, i와 i+1의 위치의 문자를 제외한 나머지로 새로운 문자열을 재정의
            s = s[:i] + s[i+2:]
            i = max(0, i-1)
        else:
            i += 1

    if s:
        return 0
    else:
        return 1

리스트를 안써도 시간초과한다.

 

 

 

 

사실 stack을 그대로 적용하면 되는 문제였다.

def solution(s):
    st = []
    
    for i in s: #마지막에 있는게 현재 문자와 같으면 pop
        if st and st[-1] == i:
            st.pop()
        else:  # 나머진 append
            st.append(i)

    if st: # stack이 남아있으면
        return 0
    else: # stack이 비어있으면
        return 1

처음에 if 조건을 잘 설정하는 것, 구현하는 것이 중요해보인다.

 

 

 

 

 

 

 

 

 

문제 12) 주식 가격
https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

저자의 풀이.. (근데 이해안감..)

def solution(prices):
  n = len(prices)
  answer = [0] * n  # ➊ 가격이 떨어지지 않은 기간을 저장할 배열

  # 스택(stack)을 사용해 이전 가격과 현재 가격을 비교
  stack = [0]  # ➋ 스택 초기화
  for i in range(1, n):
    while stack and prices[i] < prices[stack[-1]]:
      # ➌ 가격이 떨어졌으므로 이전 가격의 기간을 계산
      j = stack.pop( )
      answer[j] = i - j
    stack.append(i)
  # ➍ 스택에 남아 있는 가격들은 가격이 떨어지지 않은 경우
  while stack:
    j = stack.pop( )
    answer[j] = n - 1 - j
  return answer

 

 

 

 

 

 

 

 

 

 

문제 13) 크레인 인형 뽑기 게임  (카카오 2019 겨울 인턴)

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

프로그래머스

 

# 목표: 작동시킨 후 터져 사라진 인형의 개수 찾기
# board: 2차원 배열. 움직이는 공간. 숫자는 각 인형 type.(1~100). 0은 빈칸
# moves: 크레인 작동한 곳
# 인형이 없는데 작동한 경우 아무일도 일어나지 않는다.
# 한번 moves로 작동하면 100% 실행된다.

def solution(board, moves):
    # zip: 각 행 tuple로 전환. 여기서 *로 transpose. filter로 stack 정리
    lst = [list(filter(lambda x: x != 0, reversed(col))) for col in zip(*board)]
    st = [0]      # 바구니 설정 (비어있으면 인덱스 오류 생기므로 넣음)
    answer = 0
    for i in moves:
        if lst[i-1]: # moves의 값은 python index처럼 0부터 시작하지 않으므로 i-1
            k = lst[i-1].pop() # pop된 값 저장
            if k != st[-1]: # st의 최근값과 같은지 여부 검사
                st.append(k) # 안같으면 추가
            else:  # 같으면
                st.pop() # 최근값 pop
                answer += 2 # answer값 +2
        else: # 리스트가 비어있는경우 무시
            continue

    return answer

 

처음 주어진 배열을 zip(*리스트이름)으로 transpose하고, filter함수 내 lambda와 reversed로 stack 모양 만드는 것이 쉽지 않았던 문제이다.

 

 

 

 

 

 

 

 

문제 14) 표 편집 (카카오 2021 인턴)

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

프로그래머스

문제풀이 미완성

# "U X": 위로 X칸, "D X": 밑으로 X칸, "C": 삭제 후 바로 아래 행 선택(없으면 바로 윗행 선택) 
# "Z": 최근 삭제 행 복구. 선택 행 그대로   -> 삭제된 행을 기록하는 deque 필요
# 정수 n: 원본 표 행의 개수.  
# 정수 k: 기본 선택된 행 위치 -> 코드에서는 인덱스 위치
# cmd: 명령어들 (문자배열)   -> 명령어를 deque로 해보자
# 목표: 모든 명령어 후, 원본과 이후의 결과를 비교해서 각 행의 삭제여부 문자열로 붙여서 출력
# 행 0이 되는 경우 없음!
# 효율성 point!!: 실제 배열 바꾸는건 마지막에 저장된 인덱스로만 수행하기
from collections import deque

def solution(n, k, cmd):
    answer = ['O'] * n  # 답안 문자열(원본) 리스트로 세팅
    cmd = deque(cmd) # cmd deque화
    logs = [] # 삭제처리된 history 기록 (stack연산)
    
    while cmd: # 비어있지 않으면 계속 진행
        if 'D' in cmd[0]:
            action = cmd.popleft()
            k += int(action[1:])
            k = min(k, n - 1)
        elif 'U' in cmd[0]:
            action = cmd.popleft()
            k -= int(action[1:])
            k = max(k, 0)
        elif cmd[0] == 'C':  # 삭제하고 바로 아래 행 선택!
            cmd.popleft()
            logs.append(k) # 삭제된 것 인덱스 기록
            if 'O' not in answer[k:]:
                #k = max(i for i, val in enumerate(answer[:k]) if val == 'O')
                k = next((i for i in range(k - 1, -1, -1) if answer[i] == 'O'), k)

            else:
                k += answer[k:].index('O')                
        elif logs and cmd[0] == 'Z':
             cmd.popleft()
             logs.pop()  # popleft()아님

        else:
                continue

    
    for i in logs:  # 최종 남은 것만 갱신
        answer[i] = 'X'
    
    
    return ''.join(answer)

테스트케이스만 통과하고 실제로는 작동안되는 것이다.

 

 

 

저자의 풀이

def solution(n, k, cmd):
  # ➊ 삭제된 행의 인덱스를 저장하는 리스트
  deleted = [ ]

  # ➋ 링크드 리스트에서 각 행 위아래의 행의 인덱스를 저장하는 리스트
  up = [i - 1 for i in range(n + 2)]

  down = [i + 1 for i in range(n + 1)]

  # ➌ 현재 위치를 나타내는 인덱스
  k += 1

  # ➍ 주어진 명령어(cmd) 리스트를 하나씩 처리
  for cmd_i in cmd:
    # ➎ 현재 위치를 삭제하고 그다음 위치로 이동
    if cmd_i.startswith("C"):
      deleted.append(k)
      up[down[k]] = up[k]
      down[up[k]] = down[k]
      k = up[k] if n < down[k] else down[k]

    # ➏ 가장 최근에 삭제된 행을 복원
    elif cmd_i.startswith("Z"):
      restore = deleted.pop( ) 
      down[up[restore]] = restore
      up[down[restore]] = restore

    # ➐ U 또는 D를 사용해 현재 위치를 위아래로 이동
    else:
      action, num = cmd_i.split( ) 
      if action == "U":
        for _ in range(int(num)):
          k = up[k]
      else:
        for _ in range(int(num)):
          k = down[k]

  # ➑ 삭제된 행의 위치에 'X'를, 그렇지 않은 행의 위치에 'O'를 포함하는 문자열 반환
  answer = ["O"] * n
  for i in deleted:
    answer[i - 1] = "X"
  return "".join(answer)

 

 

조금 길게 쓴 또 다른 풀이

from collections import deque

def solution(n, k, cmd):
    answer = ['O'] * n
    cmd = deque(cmd)
    logs = []

    next_node = {i: i + 1 for i in range(n)}
    prev_node = {i: i - 1 for i in range(n)}
    next_node[n - 1] = None
    prev_node[0] = None
    for action in cmd:
        if action[0] == 'D':
            move = int(action[2:])
            for _ in range(move):
                k = next_node[k]
        elif action[0] == 'U':
            move = int(action[2:])
            for _ in range(move):
                k = prev_node[k]
        elif action[0] == 'C':
            logs.append((prev_node[k], k, next_node[k]))
            prev, next = prev_node[k], next_node[k]
            if prev is not None:
                next_node[prev] = next
            if next is not None:
                prev_node[next] = prev
            k = next if next is not None else prev
        elif action[0] == 'Z':
            prev, cur, next = logs.pop()
            if prev is not None:
                next_node[prev] = cur
            else:
                next_node[cur] = next
            if next is not None:
                prev_node[next] = cur
            else:
                prev_node[cur] = prev
    for _, cur, _ in logs:
        answer[cur] = 'X'
    return ''.join(answer)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

추천 문제1 ) 같은 숫자는 싫어!

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

프로그래머스

기본적인 스택 자료구조 구현이 가능한지 물어보는 문제이다. 앞서서 먼저 푼 크레인뽑기 인형 문제가 생각났다.

def solution(arr):
    answer = ['-'] # 빈 리스트 방지
    for i in arr:
        if answer[-1] == i:
            continue
        else:
            answer.append(i)
    return answer[1:]

문제조건에 따르면 여기선 pop을 할 필요가 없다. 그냥 반영을 안하면 되는 문제니까

또한, 첫 빈 리스트 방지에 대해서 0을 해버리니 0으로 시작하는 경우 오류가 생기므로, 절대 중복되지않을 문자를 삽입하였다. 마지막에 슬라이싱으로 출력하면 되니까. 이렇게하니 효율성테스트도 손쉽게 통과하였다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

추천 문제2 ) 올바른 괄호

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

프로그래머스

# stack idea: '('가 나오면 append.  ')'가 나오면 pop. 통이 True면(비어있지않으면) False
def solution(s):
    answer = []
    for i in s:
        if i == '(':
            answer.append(i)
        else:
            try:
                answer.pop()
            except:  # pop연산에 에러가 출력될 경우
                return False
    return False if answer else True

 

몸풀기문제 1번과 로직이 같다. 그러나 여기선 예외 처리가 중요한 문제이다.

if로 조건을 따로 빼주어서 하는 방법도 있지만 try except 방법을 처음으로(ㅎㅎ;;) 써본 문제.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

추천 문제3 ) 컨트롤 제트

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

프로그래머스

# 차례대로 더하다가 Z 나오면 해당 숫자 빼기 -> 완전 stack 그 자체
# 음수인 경우 - 부호까지 합쳐서 문자열 길이가 길어진다. -> list 변환 필요
def solution(s):
    s = list(s.split()) # 각 원소 list 변환
    answer = 0
    for i, val in enumerate(s): # 인덱스 연산이 필요하면 걍 enumerate 쓰자
        if val != 'Z': # 굳이 stack 구현안해도 조건으로 풀린다.
            answer += int(val)
        else:
            answer -= int(s[i-1])
    return answer

아이디어는 stack인데 구현하다보면 굳이 stack을 안써도 되는 듯한 문제이다.

 

 

 

def solution(s):
    s = list(s.split()) # 각 원소 list 변환
    answer = [] # 스택 구현 통
    for val in s: # 말 그대로 스택을 하나하나 구현하는 개념
        if val != 'Z':
            answer.append(int(val))
        else:
            answer.pop()
    return sum(answer)

그래도 스택을 구현하는 문제의도대로도 풀어보았다.

 

 

 

 

 

 

 

 

 

 

 

 

 

---

Chp7 큐

 

 

 

 

 

 

 

문제 15) 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

여기서 return값은 마지막에 남은 숫자로 해야하는 것이 책의 문제이다.

문제풀이 미완성

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 16) 기능 개발

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

프로그래머스

from math import ceil  # 올림 함수
from collections import deque


def solution(progresses, speeds):
    answer = []
    t = deque()
    for i in range(len(progresses)):  # 시간을 deque로 정리해 저장
        # progresses[i] + speeds[i] * x = 100
        t.append(ceil((100 - progresses[i]) / speeds[i]))

    while t:
        yardstick = t.popleft() # 비교 기준 설정
        count = 1 # 기본값 설정

        while t and yardstick >= t[0]: # 뒷작업 마무리시간보다 기준일이 높으면
            t.popleft() # 뒷 작업 popleft
            count += 1 # 개수 증가
            
        answer.append(count) # 답안 갱신

    return answer

 

이중 while문이라서 보기 안좋을(?) 수 있지만 시간복잡도가 O(N)이다.

deque도 list처럼 [] 인덱싱, 슬라이싱이 가능함을 유념하자.

 

 

 

 

 

 

 

 

 

문제 17) 카드 뭉치

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

프로그래머스

책의 풀이를 조금 변형해보았는데 25번에서 막힌다(반례포함)

from collections import deque
# 순서대로 하나씩 꺼낼 때 goal과 일치 可인지 판별

def solution(cards1, cards2, goal):
    cards1 = deque(cards1)  # 리스트를 deque로 바꿀 때 이렇게 정의한다.
    cards2 = deque(cards2)
    goal = deque(goal)

    while goal:
        yardstick = goal.popleft()  
        if cards1 and cards1[0] == yardstick:
            cards1.popleft()
        elif cards2 and cards2[0] == yardstick:
            cards2.popleft()
        else:
            break

    return "No" if goal else "Yes"
print(solution(["a", "b", "c"], ["d", "e", "f"], ["a", "d", "f"])) #No

왜 막히는지 아직 몰?루?

 

10번째 라인에서 pop을 먼저하고 있기 때문에 반례의 f 시점에서는 이미 goal은 비어있고, else block에서 card1도 card2도 f와 같지 않으므로 (각각 b, e임) break 이후 return 조건에서 goal은 이미 비어있기 때문에 잘못된 값이 나오겠네요.

 

 

책의 풀이를 따르자.

def solution(cards1, cards2, goal): # 책의 풀이와 99% 일치
    cards1 = deque(cards1) 
    cards2 = deque(cards2)
    goal = deque(goal)

    while goal:
        if cards1 and cards1[0] == goal[0]:
            cards1.popleft()
            goal.popleft()
        elif cards2 and cards2[0] == goal[0]:
            cards2.popleft()
            goal.popleft()
        else:
            break

    return "No" if goal else "Yes"

 

 

 

 

 

 

 

 

추천 문제 1) 다리를 지나는 트럭

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

프로그래머스

문제풀이 미완성