greentea31's Note

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

풀이 과정

단어를 뒤집으려면 스택에 넣었다 빼면 된다. 문자를 한글자씩 읽으면서 stack에 넣다가 tag의 시작인 '<'이나 공백 문자를 인식하면 스택에 있는 모든 문자를 스택 탑부터 출력하고, 인식한 단어를 출력하면 된다. '<'을 인식했으면 '>'을 인식하기 전까지의 단어는 스택에 넣는 과정 없이 그냥 출력해주면 된다.

코드

import sys

strInput = list(sys.stdin.readline().rstrip())
strInput.append(' ')
strInput2 = []
tagFlag = False
for i in strInput:
    if i == '<':
        while strInput2:
            print(strInput2.pop(), end='')
        tagFlag = True
        print('<', end='')
    elif i == '>':
        tagFlag = False
        print('>', end='')
    elif i == ' ':
        if tagFlag: print(' ', end='')
        else:
            while strInput2:
                print(strInput2.pop(), end='')
            print(' ', end='')
    else:
        if tagFlag: print(i, end='')
        else: strInput2.append(i)

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

풀이 과정

문자열1의 모든 단어를 스택에 넣었다가 문자열 2에 모두 pop하면 단어가 뒤집혀서 나올 것이다. 스택에 넣었다 빼는 방식으로 단어를 뒤집어도 되지만 파이썬 리스트에는 reverse()라는 리스트를 뒤집어주는 메소드가 존재한다. 입력을 리스트로 받은 뒤 메소드를 활용하고 join명령어로 문자열로 만들어서 출력하여 해결할 수 있다.

코드

import sys

T = int(sys.stdin.readline())
for i in range(T):
    beforeReverse = list(sys.stdin.readline().split())
    for j in beforeReverse:
        answer = list(j)
        answer.reverse()
        answer = ''.join(answer)
        print(answer, end=' ')
    print('')

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

풀이 과정

큐를 이용하여 문제를 해결할 수 있다. 양의 정수 K가 주어지면 줄의 맨 앞에 있는 사람을 K-1번만큼 뒤로 보낸 뒤 그 뒤에 맨 앞에 있는 사람을 줄에서 빼면 된다. 이것을 큐가 빌 때 까지 반복하면 요세푸스 순열이 구해진다.

코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
circle = deque(range(1, N+1))
answer = []

for j in range(N):
    for i in range(K-1): circle.append(circle.popleft())
    answer.append(circle.popleft())

answer = str(answer)
answer = '<' + answer[1:-1] + '>'
print(answer)

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

풀이 과정

스택은 파이썬에서 list로 구현할 수 있었지만 Queue는 list로 구현해서는 안된다. 0번째 원소를 insert, pop 하는 연산의 시간복잡도가 O(N)이기 때문에 절대 list로 큐를 구현해서는 안된다. collection 모듈에서 양 방향 큐인 deque를 사용해 큐를 구현해야 한다.

큐의 왼쪽으로 수가 들어와 오른쪽으로 나가게 구현하였고, push시 appendleft(), pop시 pop()을 사용하였다.

코드

import sys
from collections import deque

N = int(input())
queue = deque()

for i in range(N):
    instruction = sys.stdin.readline().split()
    if instruction[0] == 'push': queue.appendleft(instruction[1])
    elif instruction[0] == 'pop': print(queue.pop() if queue else -1)
    elif instruction[0] == 'size': print(len(queue))
    elif instruction[0] == 'empty': print(0 if queue else 1)
    elif instruction[0] == 'front': print(queue[-1] if queue else -1)
    elif instruction[0] == 'back': print(queue[0] if queue else -1)

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

풀이 과정

1 ~ n 까지의 수를 스택에 오름차순으로 쌓다가 필요한 수를 stack top에서 뽑아쓸 수 있다.

3, 2, 1은 스택 수열인가? push, push, push, pop, pop, pop을 하면 3, 2, 1이 나오니 스택 수열이다. 그렇다면 3, 1, 2는 스택 수열인가? push, push, push, pop까지는 했는데 stack top에 1이 있으니 2를 꺼낼 수 없으니 스택 수열이 아니다.

1. 현재의 stack top에 있는 수보다 큰 수를 꺼내야 하면 push를 계속 해서 큰 수를 쌓다가 원하는 수가 나오면 pop을 하면 된다.

2. 현재의 stack top과 같은 수를 꺼내야 하면 그냥 pop 한번 해서 수를 꺼내면 된다.

3. 현재의 stack top보다 작은 수를 꺼내야 한다면?

작은 수는 stack top 밑의 어딘가에 깔려있다. stack top을 꺼내지 않고서는 꺼낼 방법이 없다. 따라서 입력받은 수를 스택을 통해 만들면서, 현재의 stack top보다 작은 수를 요구하는 입력이 나온다면 스택 수열로 만들 수 없는 수열이라고 판단하면 된다.

코드

import sys

n = int(input())
stack = [0]
topInput = 0
noCount = False
output = []

for i in range(n):
    inPu = int(sys.stdin.readline())
    if inPu > stack[-1]:
        while inPu > stack[-1]:
            output.append('+')
            topInput += 1
            stack.append(topInput)
        output.append('-')
        del stack[-1]
    elif inPu == stack[-1]:
        output.append('-')
        del stack[-1]
    else: noCount = True

if noCount: print('NO')
else:
    for i in output:
        print(i)

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

풀이 과정

1. 문자열 도중에 )이 나온 횟수가 (이 나온 횟수보다 많아지면 안된다

2. 문자열이 끝날 때 (이 나온 횟수와 )이 나온 횟수는 같아야 한다

숫자 변수 하나 or 스택을 이용하여 위 조건을 문자열이 만족하는지 검사하면 된다. 스택을 이용하여 검사하려면 (이 나오면 원소를 하나 push, )이 나오면 원소를 하나 pop한다. 스택이 비었는데 pop을 하게 되는 문자열이면 괄호 문자열이 아니고, 문자열을 다 검사했는데 스택에 원소가 남아있으면 괄호 문자열이 아니다. 이외의 경우면 괄호 문자열이게 된다.

코드

import sys

T = int(sys.stdin.readline())

for i in range(T):
    ps = sys.stdin.readline().rstrip()
    stack = []
    noCount = False
    for j in ps:
        if j == '(':
            stack.append(1)
        elif j == ')':
            if len(stack) == 0:
                noCount = True
                break
            else: del stack[-1]

    if len(stack) == 0 and noCount == False: print('YES')
    else: print('NO')

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

풀이 과정

파이썬에서는 리스트를 스택처럼 이용할 수 있다. push 명령이 들어오면 list 끝에 붙이고, pop 명령이 들어오면 list 끝의 원소를 출력한뒤 삭제하면 된다. empty 판단은 len() 함수를 이용해서 길이가 0이면 비었다고 판단하면 된다.

이 문제는 입력의 양이 많은 문제로 input() 명령으로 입력을 받으면 시간 초과가 발생할 수 있다. input()보다 빠르게 입력을 받기 위해 sys.stdin.readline() 명령을 사용하였다.

코드

import sys

stack = []
N = int(sys.stdin.readline())

for i in range(N):
    prompt = sys.stdin.readline().rstrip()
    if prompt == 'top':
        if len(stack) == 0: print(-1)
        else: print(stack[-1])
    elif prompt == 'pop':
        if len(stack) == 0: print(-1)
        else:
            print(stack[-1])
            del stack[-1]
    elif prompt == 'size':
        print(len(stack))
    elif prompt == 'empty':
        print(1 if len(stack) == 0 else 0)
    elif prompt[:4] == 'push':
        stack.append(int(prompt[5:]))