[4월 - 코딩테스트] 스택, 큐 문제 풀이 모음

 

내가 풀이한 방법 // 나중에 복습하기 위해 코드를 정리 

 

1. 프로그래머스 올바른 괄호

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

프로그래머스

 

방법 1 : 딕셔너리 활용하기

• str_dict = { "(" : 1, ")" : -1} 을 만들어서, 최종의 합계가 0일 될 경우 True을 리턴 
• 그러나 예외상황 발생 : )()( 과 같이 ) 가 먼져오는 경우, 따라서 current value 값에서 마이너스가 되는 경우에는 ( = 닫힘 기호가 먼저 나오는 경우) 에는 False 를 리턴해줌

# 딕셔너리 활용하기
str_dict = { "(" : 1, ")" : -1}
def solution(s) :
    current_value = 0
    for i in s :
        current_value += str_dict[i]

        if current_value < 0 :
            return False

    if current_value == 0 :
        return True

 

 

방법 2 : 스택 활용하기 

• 여는 괄호가 나오면 스택에 추가, 닫는 괄호가 나오면 stack에서 제거
• 그러나, 닫는 괄호 pop 하는 경우, stack에 저장된 것이 하나도 없으면 False 를 리턴. 이 말은 닫는 괄호가 더 많다는 의미

def solution(s) :
    stack = []
    for ch in s :
        if ch == "(" :
            stack.append(ch)

        else :
            if not stack :
                return False

            stack.pop()

    return not stack

 

---

 

 

2. 프로그래머스 같은 숫자는 싫어

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

프로그래머스

 

• 이전의 숫자와 현재의 숫자가 다르면, stack 에 추가 / 혹은 스택에 비어있으면 stack에 추가
• 이전의 숫자와 현재의 숫자가 같으면 

def solution(arr):
    stack = []
    stack.append( arr[0] )

    for i in arr :
        if i != stack[-1] or len(stack) == 0:
            stack.append(i)

        else :
            stack.pop


    return stack

 

 

---

3. 프로그래머스 기능개발

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

프로그래머스

# 기능 개발

import math
def solution(progresses, speeds):
    left_time = list()
    n = len(progresses)

    # 남은 시간 리스트 생성
    for i in range(n):
        left_time.append(math.ceil((100 - progresses[i]) / speeds[i]))

    front = left_time[0]
    answer = []
    count = 1

    for i in range(1,len(progresses)) :
        if front >= left_time[i] :
            count += 1

        else :
            front = left_time[i]
            answer.append(count)
            count = 1

    answer.append(count)


    return answer

 

 

---

 

4. 백준 제로

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

n = int(input())
A = list()

for i in range(n) :
    A.append(int(input()))

stack = []

for i in range(n) :
    if A[i] != 0 :
        stack.append(A[i])

    else :
        stack.pop()

sumnumber = sum(stack)

print(sumnumber)

 

 

---

5. 백준 괄호

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

• 위의 프로그래머스 괄호 문제와 똑같이 괄호를 판별하는 함수를 만들어줌 

m = int(input())

def check(parst) :
    stack = []
    for ch in parst :
        if ch == "(" :
            stack.append(ch)

        else :
            if not stack :
                return False
            stack.pop()

    return not stack

for i in range(m) :
    answer = check(input())

    if answer == False :
        print("NO")

    else :
        print("YES")

 

 

---

6. 백준 요세푸스 문제

• deque 를 활용해서 푸는 문제
• 마지막 출력값 형태가 리스트 형태가 아니라 <> 형태라 replace 형태로 형식을 바꿔줘야함

from collections import deque
n,m = map(int, input().split())
myQueue = deque()

for i in range(n) :
    myQueue.append(i+1)

return_list = list()

while len(myQueue) > 0 :
    for j in range(m-1) :
        myQueue.append(myQueue.popleft())

    return_list.append(myQueue.popleft())
    j = 0

print(str(return_list).replace('[','<').replace(']','>'))

 

---

7. 백준 카드 2

• 큐를 이용해서 문제를 해결
• popleft을 이용하여 맨 앞장의 카드 버리기
• 위의 과정 바로 다음으로 popleft -> append를 수행하여 맨 앞에 있는 카드를 가장 아래로 옮기기 
• 큐의 크기가 1이 될 때까지 ( while len(myQueue) > 1 ) 남은 원소 출력

from collections import deque

n = int(input())
myQueue = deque()

for i in range(n) :
    myQueue.append(i+1)

while len(myQueue) > 1 :
    myQueue.popleft()
    myQueue.append(myQueue.popleft())

print(myQueue[0])

 

 

---

 

8. 프로그래머스 짝지어 제거하기

• 실수한 이유 : 다짜고자 s[i] == stack[-1] 조건 여부를 따짐 -> 처음에는 stack이 비워져 있을 것임
• 따라서, if not stack ~ 일 경우의 조건을 먼저 해줘야 함

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

def solution(s):
    stack = []

    for i in range(len(s)) :
        if not stack :
            stack.append(s[i])

        else :
            if s[i] == stack[-1] :
                stack.pop()
            else :
                stack.append(s[i])

    if stack : return 0
    else : return 1

 

---

9. 백준 덱2

• 맨 앞에 len(MyQueue) 을 변수로 정의했으면 더 짧고 깔끔하게 풀 수 있었을 듯 하다. 

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

import sys
from collections import deque
N = int(input())
MyQueue = deque()

for i in range(N) :
    A = sys.stdin.readline().strip()

    if A[0] == '1' :
        i,m = A.split()
        MyQueue.appendleft(m)

    if A[0] == '2' :
        i,m = A.split()
        MyQueue.append(m)

    if A[0] == '3' :
        if len(MyQueue) == 0 :
            print(-1)

        else :
            print(MyQueue.popleft())

    if A[0] == '4' :
        if len(MyQueue) == 0 :
            print(-1)

        else :
            print(MyQueue.pop())

    if A[0] == '5' :
        print(len(MyQueue))

    if A[0] == '6' :
        if len(MyQueue) == 0 :
            print(1)

        else :
            print(0)

    if A[0] == '7' :
        if len(MyQueue) == 0 :
            print(-1)
        else :
            print(MyQueue[0])

    if A[0] == '8' :
        if len(MyQueue) == 0 :
            print(-1)
        else :
            print(MyQueue[-1])

 

 

---

 

10. 백준 스택 2

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

import sys
N = int(input())
stack = []

for i in range(N) :
    inputnumber = sys.stdin.readline().strip()
    sizestack = len(stack)
    number = inputnumber[0]

    if number == '1' :
        stack.append(int(inputnumber.split()[1]))

    elif number == '2' :
        if sizestack == 0 :
            print(-1)
        else : print(stack.pop())

    elif number == '3' :
        print(len(stack))

    elif number == '4' :
        if sizestack == 0 : print(1)
        else : print(0)

    elif number == '5' :
        if sizestack == 0 :
            print(-1)
        else : print(stack[-1])