[백준/Python]스택, 큐, 덱 - part.1

문제

백준 단계별 풀이 - 스택, 큐, 덱
https://www.acmicpc.net/step/11

---

[28278]스택 2

문제링크: https://www.acmicpc.net/problem/28278

 

조건을 순서대로 수행하기만 하면 되는 문제다.

물 흐르듯이 따라가면 되는 문제...지만 잘못 이해한 부분이 있었다.

조건 2번을 보면, "맨 위의 정수를 빼고 출력한다."로 되어있다.
빼고(except)로 이해했건만 알고보니 빼고(pop)였다.

단계별 풀이

from sys import stdin


input = stdin.readline

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

• 우선 input을 stdin.readline함수로 선언해준다.
• 명령의 수 N의 값을 받아 정수형으로 변환.
• 스택으로 사용할 리스트 stack 생성.

for _ in range(N):
    command, *num = input().split()

• 명령의 수만큼 for문을 반복한다.
• 명령코드는 기본적으로 한개의 정수로 주어지지만, 명령 1번같은경우 명령 정수의 형태로 주어진다.
  • 나는 언패킹(*)을 사용해 *num으로 할당해줬다. 이렇게 사용할 경우 1번을 제외한 명령도 에러 없이 동작한다.
    num으로 할당할만한 데이터가 주어지지 않으면 알아서 빈 리스트가 할당되기 때문이다.

    if command == "1":
        stack.append(int(num[0]))
    elif command == "2":
        if stack:
            print(stack.pop())
        else:
            print(-1)
    elif command == "3":
        print(len(stack))
    elif command == "4":
        print(int(not stack))
    else:
        if stack:
            print(stack[-1])
        else:
            print(-1)

• 그 다음은 조건대로 작성해주면 된다. num은 리스트의 형태로 존재하므로 따로 뽑아줘야한다.

전체 코드

# 스택, 큐, 덱
# 메모리: 71112KB / 시간: 1040ms

# 2번 맨 위의 정수를 빼고 출력한다 => 맨 위의 정수를 "빼고", 그 수를 "출력한다."
from sys import stdin


input = stdin.readline

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

for _ in range(N):
    command, *num = input().split()

    if command == "1":
        stack.append(int(num[0]))
    elif command == "2":
        if stack:
            print(stack.pop())
        else:
            print(-1)
    elif command == "3":
        print(len(stack))
    elif command == "4":
        print(int(not stack))
    else:
        if stack:
            print(stack[-1])
        else:
            print(-1)

---

[10773]제로

문제링크: https://www.acmicpc.net/problem/10773

 

주어진 수들의 총 합을 구하는 문제다.

도중에 재민이녀석이 0을 외치면, 그 직전의 수를 지워주면 된다.
참고로 0 직전의 수는 무조건 존재한다.

 

간단한 문제이므로 전체 코드로 충분하다.

전체 코드

# 스택, 큐, 덱
# 메모리: 31900KB / 시간: 116ms

# 정수가 0일 경우에 지울 수 있는 수가 있음을 보장.
from sys import stdin


input = stdin.readline

K = int(input())
stack = []

for _ in range(K):
    num = int(input())

    if not num:
        stack.pop()
        continue

    stack.append(num)

print(sum(stack))

• 입력될 정수의 갯수 K만큼 아래의 for문을 반복.
• 각 정수는 int로 변환 후 num으로 할당해준다.
  • 만약 num이 아닐 경우(=num == 0일 경우), 직전의 수를 pop()한 뒤 다음 반복으로 넘긴다.
  • 그게 아니라면 stack에 그대로 더해준다.
• 반복이 끝나면 stack의 총 합을 출력.

---

[9012]괄호

문제링크: https://www.acmicpc.net/problem/9012

 

각 줄의 문자열은 두 개의 괄호 "(", ")" 로만 이루어져 있다.
짝이 안맞는다면 NO 를, 맞다면 YES 를 출력해줘야한다.

단계별 풀이

from sys import stdin


input = stdin.readline

T = int(input())

• input함수를 재정의
• 입력될 줄의 갯수를 T로 할당.

def check_ps(string) -> bool:
    stack = []

    for s in string:
        if s == "(":
            stack.append(s)
        else:
            if not stack:
                return False
            stack.pop()

    return bool(not stack)

• 해당 문자열 string이 괄호짝이 맞는지 아닌지 체크해줄 함수 check_ps를 만들어준다. 각 줄마다 체크해야하므로 따로 함수로 빼줬다.
• 먼저 빈 리스트 stack을 선언한 뒤 for문을 통해 string을 순회한다.
  • 만약 s가 여는 괄호 (라면 그대로 stack에 추가한다.
  • 닫는 괄호 )일 경우, 먼저 stack이 비어있는지 체크해야한다. 비어있는상태에서 pop()을 실행하면 에러가 나기 때문이다.
    • 만약 비어있다면 그대로 False를 반환해주고,
    • 아니라면 pop()을 실행한다. 여는 괄호 한개를 제거해줌으로써 짝을 맞춰주는거다.
• for문 순회가 끝나고도 stack이 남아있다면 False, 비어있으면 짝이 맞다는 소리이므로 True를 반환해준다.

for _ in range(T):
    ps = input().strip()  # stdin로 그냥 input값을 받아올땐 strip()을 꼭 써주자.

    print("YES" if check_ps(ps) else "NO")

• 이제 T만큼 check_ps(입력값)을 반복해준다.
• 만약 함수의 반환값이 True라면 "YES", False라면 "NO"를 반환한다.

🚨 일반적인 input()의 경우, 개행문자(\n)를 제거한 입력값을 반환해준다.
하지만 현재 input을 stdin.readline으로 할당해놓은 상태다.
readline()같은 경우 개행문자까지 포함한 값을 반환해주므로, strip()이나 rstrip()을 통해 따로 제거해주어야한다.

전체 코드

# 스택, 큐, 덱
# 메모리: 31120KB / 시간: 44ms

from sys import stdin


input = stdin.readline

T = int(input())

def check_ps(string) -> bool:
    stack = []

    for s in string:
        if s == "(":
            stack.append(s)
        else:
            if not stack:
                return False
            stack.pop()

    return bool(not stack)

for _ in range(T):
    ps = input().strip()  # stdin로 그냥 input값을 받아올땐 strip()을 꼭 써주자.

    print("YES" if check_ps(ps) else "NO")

---

[4949]균형잡힌 세상

문제링크: https://www.acmicpc.net/problem/4949

 

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

 

즉 (공백).도 True로 취급된다.

단계별 풀이

from sys import stdin


input = stdin.readline

brackets = {"(": ")", "[": "]"}

• input함수 재정의.
• 괄호들을 딕셔너리 brackets에 저장한다. 여는괄호를 key, 닫는괄호를 value로 지정해줬다.

def check_balanced(string) -> bool:
    stack = []

    for s in string:
        if s in brackets:
            stack.append(s)
        elif s in brackets.values():
            if not stack:
                return False

            p = stack.pop()
            if brackets[p] != s:
                return False
    return bool(not stack)

• 괄호짝이 맞는지 아닌지 체크해줄 함수 check_balanced를 생성해준다.
• 함수 호출 시 스택 stack을 생성한 뒤, 입력받은 문자열 string에 대해서 순회를 시작한다.
  • 만약 s가 brackets의 key값에 존재한다면(여는괄호라면), stack에 추가한다.
  • 하지만 brackets의 value값들에 존재할경우(닫는괄호),
    • stack이 비어있다면 바로 False를 반환해준다.
    • 아니라면 stack을 pop()한 값(여는괄호)을 brackets에 넣어 비교해본다.
      만약 현재 문자열 s가 p의 value값과 같지 않다면 괄호짝이 맞지 않다는 소리이므로 False를 반환해준다.
• 모든 순회를 마치고도 stack이 남아있다면 False, 비어있다면 True를 반환한다.

while True:
    sentence = input().rstrip()

    if sentence == ".":
        break

    print("yes" if check_balanced(sentence) else "no")

• 위의 check_balanced()함수를 while문을 통해 반복 실행한다.

🚨 참고로 입력값.rstrip()을 해줘야 개행문자 없이 온전한 문자열로 저장된다.
(해당 문제에서는 그냥 공백+온점 도 입력값으로 주어지므로, strip()은 사용 X. 양쪽 공백이 지워지므로 입력 끝값(.)으로 인식해버린다.)

• 공백, 다른 문자 없이 온점만 입력될경우 입력 끝이라는 소리이므로 break.
  그 전까지는 check_balanced(입력값.rstrip())을 실행한다.
• 반환값이 참이라면 "yes", 거짓이라면 "no"를 출력.

전체 코드

첫번째 코드

# 스택, 큐, 덱
# 메모리: 31120KB / 시간: 72ms

from sys import stdin


input = stdin.readline

brackets = {"(": ")", "[": "]"}

def check_balanced(string) -> bool:
    stack = []

    for s in string:
        if s in brackets:
            stack.append(s)
        elif s in brackets.values():
            if not stack:
                return False

            p = stack.pop()
            if brackets[p] != s:
                return False
    return bool(not stack)

while True:
    sentence = input().rstrip()

    if sentence == ".":
        break

    print("yes" if check_balanced(sentence) else "no")

 

두번째 코드(시간이 좀 더 단축됨)

# 시간: 60ms
from sys import stdin


brackets = {")": "(", "]": "["}

def is_balanced(s):
    stack = []
    for char in s:
        if char in "([":
            stack.append(char)
        elif char in ")]":
            if not stack or stack.pop() != brackets[char]:
                return False
    return not stack

for line in stdin:
    line = line.rstrip()
    if line.rstrip() == ".":
        break
    print("yes" if is_balanced(line) else "no")

---

[12789]도키도키 간식드리미

문제링크: https://www.acmicpc.net/problem/12789

 

입력값으로 정수 N, 그리고 1부터 N까지의 수로 이루어진 문자열이 주어진다.
스택을 사용하여 이 문자열이 1,2,3...N 이 될 수 있는지 체크하는 문제.

단계별 풀이

from sys import stdin


input = stdin.readline

N = int(input())
students = list(map(int, input().split()))
stack = []
order = 1

• 먼저 input 재정의.
• students = 입력값들을 int형으로 변환한 리스트.
• 스택으로 사용할 빈 리스트 stack 생성.
• 1번부터 차례대로 배정받아야하니 order = 1로 현재 순번을 정의해준다.

for student in students:
    if student == order:
        order += 1
        while stack and stack[-1] == order:
            stack.pop()
            order += 1
    else:
        stack.append(student)

• 입력받은 정수형 리스트 students를 하나씩 순회한다.
  • 만약 현재 순번(order)와 현재 학생의 순번이 일치하다면, order을 1 증가시켜준다.
  • 그리고 stack이 존재, stack의 마지막값이 현재 순번과 일치하는동안 pop()으로 꺼낸 후 order을 1 증가시킨다.

❗ 예시 데이터 5 4 1 3 2를 예로 들어보자.

1. 학생의 순번 5 != 현재 순번 1 => stack.append(5)
2. 학생의 순번 4 != 현재 순번 1 => stack.append(4)
3. 학생의 순번 1 == 현재 순번 1 => order += 1 => 현재 순번 2
   => stack[-1](=4) != 현재 순번 2 => while문 진입 X
4. 학생의 순번 3 != 현재 순번 2 => stack.append(3)
5. 학생의 수번 2 == 현재 순번 2 => order += 1 => 현재 순번 3
   => stack[-1](=3) == 현재 순번 3 => stack.pop, order += 1 => 현재 순번 4
   => stack[-1](=4) == 현재 순번 4 => stack.pop, order += 1 => 현재 순번 5
   => stack[-1](=5) == 현재 순번 5 => stack.pop, order += 1 => 현재 순번 6
   => stack이 비었으므로 while문 탈출
   => for문 순회 완료

print("Nice" if not stack else "Sad")

• for문 순회 후 stack이 비어있다면 "Nice", 남아있다면 "Sad"를 출력한다.
  위의 예시 데이터의 경우 "Nice"가 출력되겠다.

전체 코드

# 시간: 32ms
from sys import stdin


input = stdin.readline

N = int(input())
students = list(map(int, input().split()))
stack = []
order = 1

for student in students:
    if student == order:
        order += 1
        while stack and stack[-1] == order:
            stack.pop()
            order += 1
    else:
        stack.append(student)

print("Nice" if not stack else "Sad")