✅ 문제 풀이 - 자료구조
🎈 1158 요세푸스 문제
양의 정수 N, K가 주어지고 N명의 사람들이 원을 이루며 앉아있을 때 K번째 사람을 원에서 제거하려 한다. 이때 원에서 사람들이 제거되는 순서를 순열로 나열한 것을 요세푸스 순열이라고 하는데, 해당 순열을 구하는 문제
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
array = [i for i in range(1, n+1)]
answer = []
idx = 0
for i in range(n):
idx += k-1
if idx >= len(array):
idx %= len(array)
answer.append(str(array.pop(idx)))
print('<', ', '.join(answer), '>', sep='')< 풀이 과정 >
n, k를 입력받고 n명의 사람들을 array 배열로 나타낸 후 제거될 사람들의 인덱스 번호를 idx로 나타내 k-1만큼 더하며 길이가 len(array)보다 크거나 같다면 나머지로 변환하며 answer에 append해준다.
최종적으로 < > 구조로 값을 나타내기 위해 answer를 str형태로 나타내준다. sep를 안해준다면 < 3, 2 >와 같이 띄어쓰기가 나타나므로 sep=''로 나타낸다.
🎈 10866 덱
정수를 저장하는 deque를 다음 명령어로 구현한다.
- push_front x : 정수 x를 덱 앞에 넣는다
- push_back x : 정수 x를 덱 뒤에 넣는다
- pop_front : 덱 가장 앞의 수를 빼고 출력, 덱에 정수가 없다면 -1 출력
- pop_back : 덱 가장 뒤의 수를 빼고 출력, 덱에 정수가 없다면 -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 i in range(n):
word = input()
command = word.split()
if command[0] == 'push_front':
queue.appendleft(command[1])
elif command[0] == 'push_back':
queue.append(command[1])
elif command[0] == 'pop_front':
if not queue:
print('-1')
else:
print(queue[0])
queue.popleft()
elif command[0] == 'pop_back':
if not queue:
print('-1')
else:
print(queue[len(queue)-1])
queue.pop()
elif command[0] == 'size':
print(len(queue))
elif command[0] == 'empty':
if not queue:
print('1')
else:
print('0')
elif command[0] == 'front':
if not queue:
print('-1')
else:
print(queue[0])
elif command[0] == 'back':
if not queue:
print('-1')
else:
print(queue[len(queue)-1])< 풀이 과정 >
queue라는 deque을 만든 후 주어진 명령어대로 수행한다. appendleft, popleft를 활용하여 가장 맨 뒤, 앞을 출력한다.
🎈 10799 쇠막대기
()는 레이저를 표현하고 쇠막대기의 왼쪽 끝은 (로 오른쪽 끝은 )로 표현된다.
쇠막대기와 레이저가 주어질 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 문제
import sys
input = sys.stdin.readline
razor = list(input().strip())
answer = 0
stack = []
for i in range(len(razor)):
if razor[i] == '(':
stack.append(razor[i])
else:
if razor[i-1] == '(':
stack.pop()
answer += len(stack)
else:
stack.pop()
answer += 1
print(answer)< 풀이 과정 >
스택을 이용하여 해결한 문제로, 다음과정을 반복한다
1. 현재 razor의 값이 ( 라면 stack에 넣는다.
2. 이전 razor값이 ) 이고 현재 razor값이 ( 라면 stack은 pop하고 현재 스택 길이 만큼 answer에 더해준다
3. 이전 razor값이 )이고 현재 값도 ) 라면 stack은 pop하고 answer에 1만 더해준다.
🎈 11286 절댓값 힙
첫 줄에 연산 수가 주어지고 다음 n개의 줄에 연산 정보를 나타내는 정수 x가 주어진다.
x가 0이라면 배열에서 가장 작은 절댓값을 출력하고 그 값을 배열에서 제거한다.
x가 0이 아니라면 배열에 x라는 값을 넣는 연산을 한다.
import heapq
import sys
input = sys.stdin.readline
n = int(input())
heap = []
for _ in range(n):
num = int(input())
if num != 0:
heapq.heappush(heap, (abs(num), num))
else:
if not heap:
print(0)
else:
print(heapq.heappop(heap)[1])< 풀이 과정 >
heapq를 구현한 풀이로, for문으로 n만큼 정수를 입력받는다.
입력받은 정수 num이 0이 아니면 heappush를 해주는데 heap을 튜플로 구성하여 맨 앞 숫자(절댓값)만 가지고 정렬하도록 만들어준다.
입력받은 num이 0인 경우 heap이 비어있다면 0을 출력하고 heap이 비어있지 않으면 heappop으로 가장 작은 절댓값을 가진 해당 정수를 출력해준다.
🎈 1021 회전하는 큐
n개의 원소를 포함한 양방향 순환 큐를 가지고 3가지 연산을 진행한다.
1. 첫번째 원소를 뽑아낸다 (a1..ak >> a2..ak,a1)
2. 왼쪽으로 한 칸 이동 (a1...ak >> a2..ak,a1)
3. 오른쪽으로 한 칸 이동 (a1...ak >> ak, a1...ak-1)
첫 줄에 큐 크기 n, 뽑아내고자 하는 수 m이 주어지고 둘째 줄에는 뽑는 수의 위치가 순서대로 주어질 때 정답을 구하시오
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
idx = list(map(int, input().split()))
queue = deque([i for i in range(1, n+1)])
answer = 0
for i in idx:
while True:
if queue[0] == i:
queue.popleft()
break
else:
if queue.index(i) <= len(queue)//2:
queue.rotate(-1)
answer += 1
else:
queue.rotate(1)
answer += 1
print(answer)< 풀이 과정 >
deque를 활용하여 풀이하였다.
1. 찾고자 하는 위치를 idx로 입력받고 n개의 원소 배열을 queue로 구현한다.
2. for문으로 idx를 돌며 while 문으로 반복하는데 queue의 제일 왼쪽 값이 idx 내 원소와 일치하면 break한다.
3. 그렇지 않다면 queue길이 절반 보다 현 위치가 작으면 왼쪽으로 돌면 더 빠르게 제일 왼쪽으로 이동시킬 수 있고, 반대의 경우 오른쪽으로 돌면 된다.
참고 사항
deque의 경우 rotate함수를 통해 -1이면 왼쪽으로, 1이면 오른쪽으로 회전이 가능하다.
