이번 주 스터디에서는 자료구조 중 스택과 큐에 대해 공부하고 문제를 풀어보는 시간을 가졌습니다.

전에도 스택과 큐에 대해서 공부해봤기 때문에 구조적인 측면에서 이해는 문제가 없었습니다.

하지만 파이썬으로 구현했던 거라 자바로 구현하려고 하니 '어떤 클래스를 사용하고 어떤 메서드를 사용하지?'라는 생각이 들었습니다.

그래서 이걸 간단히 정리해 보려고 합니다.

스택과 큐의 자료구조와 메서드에 대해 정리하겠습니다.

스택(Stack)

스택은 LIFO(Last In First Out)의 특징을 가지고 있습니다.

이건 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 말합니다.

다르게 표현하면 가장 먼저 들어간 데이터가 가장 마지막으로 나오는 것을 뜻하기도 합니다.

재귀적인 함수, 알고리즘에 사용됩니다.

데이터를 삽입 및 삭제에 O(1), 탐색에 O(n) 시간이 걸립니다.

자바에서는 Stack 클래스를 구현하여 제공합니다.

Stack 클래스 메서드는 아래와 같습니다.

Stack<Integer> st = new Stack<Integer>();

큐(Queue)

큐는 FIFO(First In First Out)의 특성을 가지고 있습니다.

이는 먼저 집어넣은 데이터가 먼저 나오는 성질을 말합니다.

때문에 데이터를 집어넣으면 뒤부터 순차적으로 생성되고 

뺄 때는 가장 처음 데이터부터 나오게 됩니다.

삽입 및 삭제에 O(1), 탐색에 O(n)의 시간이 걸립니다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬

너비 우선 탐색(BFS), 캐시 등에 사용됩니다.

자바에서 큐의 경우에는 클래스가 아닌 인터페이스를 제공합니다.

물론 구현해 놓은 클래스도 있기 때문에 그중 하나를 사용하면 됩니다.

예시로 ArrayDeque, ConcurrentLinkedDeque, LinkedList가 있습니다.

Deque의 경우에는 앞뒤로 데이터를 넣고 빼는 메서드를 가지고 있습니다.

메서드는 아래와 같습니다.

위 세 개와 아래 세 개의 메서드는 같은 기능을 하지만 오류를 반환하고 하지 않는 차이가 있습니다.

Queue<Integer> q = new LinkedList<Integer>()

2022.02.15

백준 10773 제로

# 10773 제로
import sys
K = int(input())
num =[0]

for i in range(K):
    r = int(sys.stdin.readline())
    if r == 0:
        num.pop()
    else:
        num.append(r)
print(sum(num))

반복적으로 입력받아야 하는 K의 숫자 범위가 커서 sys를 사용했다.

스택으로 쉽게 풀 수 있는 문제로 입력받은 숫자를 리스트에 하나씩 넣어주다가

0을 입력받으면 최근에 입력받은 숫자를 pop으로 추출하면 된다.

2022.02.08

백준 1874 스택수열

# 1874 스택수열
import sys

n = int(input())
stack = []
result = []
s = 0
for i in range(1,n+1):
    a = int(sys.stdin.readline())
    stack.append(a)
    if s - a < 0:
        for j in range(abs(s-a)):
            result.append('+')
        result.append('-')
        s = a
    else:
        if s - a > 1 and (s - 1) not in stack:
            result.append('NO')
            break
        else:
            result.append('-')
            s = max(a,s)
if 'NO' in result:
    print('NO')
else:
    for i in result:
        print(i)

입력받는 값을 저장하는 stack 리스트와 기호를 저장하는 result 리스트를 생성하고

s의 값을 변경해주면서 그 차이를 통해 result에 기호를 저장해줬다.

성공이라고 돼있어서 아 전에 풀어본 문제구나 하고 봤더니

전혀 기억이 안 나고 마치 새로운 문제를 보는 것 같았다.

어찌어찌 풀기는 했지만 시간 초과가 떠서 pypy3로 채점을 했다.