Jinho Tech

기본적인 덱 문제이다.

from collections import deque

N, M = map(int, input().split())
li = list(map(int, input().split()))
queue = deque(range(1, N+1))
cnt = 0
for n in li:
    while queue[0] != n:
        t = queue.index(n)
        if t <= len(queue)-t-1:
            queue.append(queue.popleft())
        else:
            queue.appendleft(queue.pop())
        cnt += 1
    queue.popleft()
print(cnt)

기본적인 큐 문제이다.

import sys
from collections import deque

N = int(sys.stdin.readline())
queue = deque()
while 1:
    n = int(sys.stdin.readline())
    if n == -1:
        break
    if n != 0 and len(queue) < N:
        queue.append(n)
    elif n == 0:
        queue.popleft()
if queue:
    print(*queue)
else: 
    print("empty")

스택과 큐를 둘 다 사용해야 되는 문제이다.

처음에 실수로 문제를 좀 어렵게 생각해서 푸는데 오래 걸렸다. 쉽게 생각하도록 하자!

큐가 없을 때까지 반복 ->  큐의 맨 처음 값이 i가 아니라면 스택에 추가 ->

스택의 맨 마지막 값이 i가 아닐 때까지 pop -> 마지막에 스택이 남아있다면 "Sad", 없다면 "Nice" 출력

from collections import deque

N = int(input())
queue = deque(map(int, input().split()))
stack = deque()
i = 1
while queue:
    if queue and queue[0] == i:
        queue.popleft()
        i += 1
    else:
        stack.append(queue.popleft())
    while stack and stack[-1] == i:
        stack.pop()
        i += 1
        
print("Nice" if not stack else "Sad")

큐 문제이다. 10845번 큐와 같은 문제이다.

이 문제는 collections.deque와 sys.stdin.readline을 사용해서 풀지 않으면 시간 초과가 나온다. 주의하자.

import sys
from collections import deque

class Queue():
    def __init__(self):
        self.li = deque()
    
    def push(self, n):
        self.li.append(n)

    def pop(self):
        print(self.li.popleft() if self.li else -1)
    
    def size(self):
        print(len(self.li))

    def empty(self):
        print(0 if self.li else 1)
        
    def front(self):
        print(self.li[0] if self.li else -1)
        
    def back(self):
        print(self.li[-1] if self.li else -1)

queue = Queue()
for _ in range(int(sys.stdin.readline())):
    s = sys.stdin.readline().split()    
    if s[0] == "push":
        queue.push(int(s[1]))
    elif s[0] == "pop":
        queue.pop()
    elif s[0] == "size":
        queue.size()
    elif s[0] == "empty":
        queue.empty()
    elif s[0] == "front":
        queue.front()
    elif s[0] == "back":
        queue.back()

순환큐 문제이다. 11866번 요세푸스 문제 0과 같은 문제이다.

11866번은 그냥 리스트로 큐를 구현해서 풀어도 맞았었는데 이 문제는 시간초과가 나와서 

속도가 매우 빠른 collections.deque를 사용했다. 

from collections import deque

N, K = map(int, input().split())
queue = deque([i for i in range(1, N+1)])
res = []
for _ in range(N):
    for i in range(K-1):
        queue.append(queue.popleft())
    res.append(queue.popleft())
print('<', end='')
print(*res, sep=', ', end='')
print('>')

브루트포스 알고리즘 & 구현 문제이다.

높이의 범위가 정해져 있어서 257가지(0~256)의 시간을 다 확인해보면 쉽게 풀 수 있다.  

sys.stdin.readline을 사용해야 하고 PyPy3로 제출해야 통과된다. 

import sys

N, M, B = map(int, sys.stdin.readline().split())
li = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
time, height = 9223372036854775807, 0
for h in range(257):
    bot = top = 0
    for i in range(N):
        for j in range(M):
            if li[i][j] < h:
                bot += h-li[i][j]
            else:
                top += li[i][j]-h
    if bot > top + B:
        continue
    t = bot + top*2
    if t <= time:
        time = t
        height = h
print(time, height)

스택 문제이다. 주의해야 될 점이 참 많은 문제다. 그래서 엄청 많이 틀렸다. 

마지막 스택에 '(', '['가 들어있다면 잘못된 형태이므로 0을 출력,

그렇지 않다면 숫자들만 있는 것이기 때문에 스택의 합을 출력해주면 된다.

def solution(s):
    stack = []
    for c in s:
        if c == ')':
            t = 0
            while stack:
                top = stack.pop()
                if top == '(':
                    stack.append(2 if t == 0 else t*2)
                    break
                elif top == '[':
                    return 0
                else:
                    t += top
        elif c == ']':
            t = 0
            while stack:
                top = stack.pop()
                if top == '[':
                    stack.append(3 if t == 0 else t*3)
                    break
                elif top == '(':
                    return 0
                else:
                    t += top
        else:
            stack.append(c)
        
    return stack

s = input()
stack = solution(s) 
if stack == 0:
    stack = []
print(0 if '(' in stack or '[' in stack else sum(stack))

숫자들이 담긴 큐와, 인덱스들이 담긴 리스트를 같이 사용해서 풀어야 하는 문제이다.

from collections import deque

for _ in range(int(input())):
    N, M = map(int, input().split())
    queue = deque(map(int, input().split()))
    index = [0 for _ in range(N)]
    index[M] = 1
    cnt = 0
    while 1:
        if queue[0] == max(queue):
            if index[0] == 1:
                break
            else:
                queue.popleft()
                index.pop(0)
                cnt += 1
        else:
            queue.append(queue.popleft())
            index.append(index.pop(0))
    print(cnt+1)

기본적인 큐 문제이다.

그냥 리스트로 큐를 구현해서 풀려고 하면 시간 초과가 나와서 collections.deque를 사용해서 풀었다.

collections모듈 안의 deque가 CPython으로 구성되어 있어서 그런지 속도면에서 압도적으로 빠른 것 같다. 

from collections import deque

N = int(input())
queue = deque([i for i in range(1, N+1)])
while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())
print(*queue)

기본적인 큐 문제이다. 순환큐!

N, K = map(int, input().split())
queue = [i for i in range(1, N+1)]
res = []
for _ in range(N):
    for i in range(K-1):
        queue.append(queue.pop(0))
    res.append(queue.pop(0))
print('<', end='')
print(*res, sep=', ', end='')
print('>')

스택을 활용해서 풀어야 하는 문제이다. for 문을 두 번 써서 풀면 절대 통과할 수가 없다. 

import sys

N = int(sys.stdin.readline())
li = [int(sys.stdin.readline()) for _ in range(N)]
stack, res = [], 0
for i in range(N):
    while stack != [] and stack[-1] <= li[i]:
        stack.pop()
    stack.append(li[i])
    res += len(stack)-1
print(res)

EX) li = [10, 3, 7, 4, 10, 2]

i = 0 -> stack = [10], res = 0

i = 1 -> stack = [10, 3], res = 1

i = 2 -> stack = [10, 7], res = 2

i = 3 -> stack = [10, 7, 4], res = 4

i = 4 -> stack = [12], res = 4

i = 5 -> stack = [12, 2], res = 5

답: 5

큐(Queue)는 FIFO구조로 먼저 집어넣은 데이터를 가장 먼저 뺄 수 있는 데이터 구조이다.

나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념이다. 덱(Deque)은 양쪽 끝에서 삽입과 삭제가

모두 가능한 자료구조인데, 큐와 스택을 합친 형태라고 생각하면 쉽다. 아래 코드는 큐 코드 예시이다.

큐 구현 문제(10845번 큐)

import sys

class Queue():
    def __init__(self):
        self.li = []
    
    def push(self, n):
        self.li.append(n)

    def pop(self):
        print(self.li.pop(0) if self.li else -1)
    
    def size(self):
        print(len(self.li))

    def empty(self):
        print(0 if self.li else 1)
        
    def front(self):
        print(self.li[0] if self.li else -1)
        
    def back(self):
        print(self.li[-1] if self.li else -1)

queue = Queue()
for _ in range(int(sys.stdin.readline())):
    s = sys.stdin.readline().split()
    if s[0] == "push":
        queue.push(int(s[1]))
    elif s[0] == "pop":
        queue.pop()
    elif s[0] == "size":
        queue.size()
    elif s[0] == "empty":
        queue.empty()
    elif s[0] == "front":
        queue.front()
    elif s[0] == "back":
        queue.back()

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/798

jinho-study.tistory.com/800

jinho-study.tistory.com/802

jinho-study.tistory.com/803

jinho-study.tistory.com/804

jinho-study.tistory.com/807

jinho-study.tistory.com/808

jinho-study.tistory.com/809

jinho-study.tistory.com/810

jinho-study.tistory.com/811

jinho-study.tistory.com/812

jinho-study.tistory.com/813

jinho-study.tistory.com/814

jinho-study.tistory.com/815

jinho-study.tistory.com/816

jinho-study.tistory.com/821

기본적인 큐 문제이다. sys.stdin.readline을 사용하지 않으면 시간 초과가 나온다.

import sys

class Queue():
    def __init__(self):
        self.li = []
    
    def push(self, n):
        self.li.append(n)

    def pop(self):
        print(self.li.pop(0) if self.li else -1)
    
    def size(self):
        print(len(self.li))

    def empty(self):
        print(0 if self.li else 1)
        
    def front(self):
        print(self.li[0] if self.li else -1)
        
    def back(self):
        print(self.li[-1] if self.li else -1)

queue = Queue()
for _ in range(int(sys.stdin.readline())):
    s = sys.stdin.readline().split()
    if s[0] == "push":
        queue.push(int(s[1]))
    elif s[0] == "pop":
        queue.pop()
    elif s[0] == "size":
        queue.size()
    elif s[0] == "empty":
        queue.empty()
    elif s[0] == "front":
        queue.front()
    elif s[0] == "back":
        queue.back()

그리디 알고리즘 & 스택 문제이다. 스택을 활용하지 않으면 시간 초과가 나온다. 

제일 큰 수로 만들려면 앞에 있는 작은 수부터 없애버려야 한다는 점이 핵심인 것 같다.

N, K = map(int, input().split())
li = list(input())
k, stack = K, []
for i in range(N):
    while k > 0 and stack and stack[-1] < li[i]:
        stack.pop()
        k -= 1
    stack.append(li[i])
print(''.join(stack[:N-K]))

스택을 활용해서 풀어야 되는 문제이다. 리스트 안에 여러 개의 스택이 들어있는 구조이다.

else문 안에 있는 아래 코드를 생각하지 못해서 계속 틀렸었다. 

if li[i] != [] and li[i][-1] == p:
	continue

해답 코드

import sys

N, P = map(int, sys.stdin.readline().split())
li = [[] for _ in range(6)]
res = 0
for _ in range(N):
    i, p = map(int, sys.stdin.readline().split())
    i -= 1
    if li[i] == [] or li[i][-1] < p:
        li[i].append(p)
        res += 1
    else:
        while li[i] != [] and li[i][-1] > p:
            li[i].pop()
            res += 1
        if li[i] != [] and li[i][-1] == p:
            continue
        li[i].append(p)
        res += 1
print(res)