3/17 Coding Test - BOJ

✅ 문제 풀이 - 자료구조

🎈 18258 큐2

첫 줄에 명령 수 n이 주어지고 n줄에 걸쳐 명령이 하나씩 주어질 때 다음 명령을 수행한 후 각 명령이 수행될 때마다 결과를 한 줄 씩 출력하는 문제. 명령은 다음과 같다.

• push X : 정수 X를 큐에 넣는 연산
• pop : 큐에서 가장 앞에 정수를 빼고 출력, 큐가 비어있다면 -1 출력
• size : 큐에 들어있는 정수 개수 출력
• empty : 큐가 비어있다면 1, 비어있지 않으면 0 출력
• front : 큐의 가장 앞의 정수 출력, 큐가 비어있다면 -1 출력
• back : 큐의 가장 뒤에 있는 정수 출력, 큐가 비었다면 -1 출력

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
queue = deque()
for _ in range(n):
    command = input().split()
    if command[0] == 'push':
        queue.append(command[1])
    elif command[0] == 'pop':
        if queue:
            print(queue.popleft())
        else:
            print(-1)
    elif command[0] == 'size':
        print(len(queue))
    elif command[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)
    elif command[0] == 'front':
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif command[0] == 'back':
        if queue:
            print(queue[-1])
        else:
            print(-1)

< 풀이 과정 >
FIFO 구조인 큐를 그대로 deque으로 구현한 문제
주어진 명령어를 그대로 popleft, append, [0], [-1] 등 인덱싱을 활용하여 구현하면 된다.

🎈 17298 오큰수

크기가 n인 수열 A가 있을 때, 각 원소 Ai에 대해 오큰수 NGEi를 구하는 문제.
오큰수란 해당 원소보다 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수를 의미하고 만일 그런 수가 없다면 -1을 의미한다.
즉, 해당 원소보다 값이 크지만 오른쪽 중 가장 왼쪽에 위치한 원소를 출력하는 문제
주의해야 하는 부분 n의 범위는 [1, 1,000,000]

import sys
input = sys.stdin.readline

n = int(input())
seq = list(map(int, input().split()))
stack = []
answer = [-1] * n

for i in range(n):
    while stack and seq[stack[-1]] < seq[i]:
        answer[stack.pop()] = seq[i]
    stack.append(i)
print(*answer)

< 풀이 과정 >
n의 범위를 보자마자 2중 for문이 아닌 stack으로 구현해야 겠다는 생각이 들었다.
for문으로 인덱스를 i로 지정하고, stack에 해당 인덱스 i를 append해준다.
while문으로, stack이 비어있지 않고 seq[스택 끝 값=인덱스] 가 현재 seq[i]보다 작다면 원소 Ai 보다 크지만, 가장 왼쪽에 있는 수가 seq[i]가 되므로 정답인 answer 리스트에 해당 seq[i]를 추가한다.
최종적으로 숫자만 출력되길 원하므로 *list 형태로 원소 값만 뽑아내 출력한다.