greentea31's Note

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

풀이 과정

오큰수 문제와 비슷하게 접근하면 된다. 수열 A에 등장한 횟수를 배열에 저장하고, 오등큰수를 찾지 못한 수의 index를 스택에 저장한다. 그리고 다음 수를 인식하면서 stack top의 index에 해당하는 수보다 등장 횟수가 더 많으면 그 index의 해당하는 수의 오등큰수를 바꿔주면 된다.

코드

import sys

N = int(input())
A = list(map(int, input().split()))

NGF = [-1] * N
F = [0] * 1000010

stack = []

for i in A:
    F[i] += 1

for i in range(N):
    while len(stack) and F[A[i]] > F[A[stack[-1]]]:
        NGF[stack.pop()] = A[i]
    stack.append(i)

for i in NGF:
    print(i, end=' ')

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

풀이 과정

문제를 다 읽으면 수열을 다 입력받은 상태에서 Ai의 다음 원소부터 끝까지 검색하면서 Ai보다 큰 수가 보이면 바로 출력해주는 방식이 떠오르지만 이 방법은 O(N^2) 방법이고, A의 크기가 100만이므로 시간 제한 1초 내로 해결할 수 없다.

스택을 이용한 더 효율적인 방법으로 풀어보자. 스택을 하나 생성하고, 오큰수가 담겨있는 배열 NGE를 만들고 -1로 초기화 하자.

입력 배열 A의 첫 번째 원소부터 살펴보면서 오큰수를 아직 못 찾은 수의 index를 스택에 저장하면서, 다음 index j를 확인했을 때 스택탑의 index i와 비교해 Ai < Aj이면 NGE[i] = Aj로 두고 스택에서 원소를 꺼내는 과정을 Ai < Aj가 아닐 때까지 반복해주자. 이러면 A의 원소에 대해 존재하는 모든 오큰수가 구해진다.

왜 이러한 방법이 성립할까? 스택에서 더 작은 수의 index일수록 위에 담겨있기 때문이다. 더 큰 수의 index는 i의 오큰수가 되어서 스택에 들어오지 않고 기존 수보다 더 작은 수의 index만 스택에 쌓여간다.

코드

import sys

N = int(input())
A = list(map(int, input().split()))
NGE = [-1 for x in range(N)]
stack = []

for j in range(N):
    if len(stack) == 0:
        stack.append(j)
        continue
    i = stack[-1]
    while A[i] < A[j]:
        NGE[i] = A[j]
        stack.pop()
        if len(stack) == 0: break
        else: i = stack[-1]
    stack.append(j)

for i in range(N): print(NGE[i], end=' ')

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

풀이 과정

count = 아직 안끝난 쇠막대기의 개수

answer = 정답 이라고 하자.

'(' 인식시 일단 쇠막대기의 시작이라고 간주 => count += 1

')' 인식시 앞 문자가 '('이면 앞의 '('이 쇠막대기의 시작이 아니였으므로 count -= 1, 그 후 안끝난 쇠막대기들 자르니까 answer += count를 해주고, 앞 문자가 '('이 아니면 쇠막대기의 끝이므로 count -= 1, answer += 1를 해주면 된다.

코드

import sys

solve = list(input())
count = 0
answer = 0
for i in solve:
    if i == '(':
        count += 1
    elif i == ')':
        if stack[-1] == '(':
            count -= 1
            answer += count
        else:
            count -= 1
            answer += 1

print(answer)

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:]))