│문제
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
│풀이 (Python)
from collections import deque
import sys
Deque=deque()
N=int(input())
def empty():
if len(Deque)==0:return 1
else:return 0
for i in range(N):
order=sys.stdin.readline().split()
if "push_front" in order:
Deque.appendleft(order[1])
elif "push_back" in order:
Deque.append(order[1])
elif "pop_front" in order:
if empty():
print(-1)
else:
print(Deque[0])
Deque.popleft()
elif "pop_back" in order:
if empty():
print(-1)
else:
print(Deque[-1])
Deque.pop()
elif "size" in order:print(len(Deque))
elif "empty" in order:print(empty())
elif "front" in order:
if empty():print(-1)
else:print(Deque[0])
elif "back" in order:
if empty():print(-1)
else:print(Deque[-1])
│설명 (Python)
덱( deque)은 Double- Ended-Queue의 약자로, 앞과 뒤로 둘 다 삽입 삭제가 가능한 큐 자료구조이다.
keypoint 1- deque라이브러리 활용
from collections import deque
파이썬에서 덱은 기본라이브러리를 통해 import 하여 사용할 수 있다.
Deque=deque() deque변수에 파이썬 리스트와 비슷하게 선언하여 사용할 수 있고,
리스트에서 기본적으로 제공하는 append , extend, remove, clear, index 등 많은 메서드를 활용할 수 있다.
10866번 덱 문제를 풀기 위해서는
Deque.appendleft(order[1]) 덱의 0번째에 원소를 추가,
Deque.append(order[1]) 덱의 마지막에 원소를 추가,
Deque.popleft() 덱의 앞에서 원소를 제거,
Deque.pop() 덱의 마지막에서 원소를 제거하는 메서드들을 활용하여 문제를 풀어가면 된다.
keypoint 2- empty함수 활용
pop_front, pop_back, front, back 등 다양한 함수에서 "비어있다면 -1 출력" 조건을 처리할 때 매 함수에서 비어있는지 검사하는 것이 아닌 이미 있는 기능인 empty함수를 채용해 코드가 더 깔끔하게 작성할 수 있다.
명령어 order 변수 안에 원하는 명령이 있는지 확인하기 위하여 in연산자를 활용하여 풀이하였다.
│풀이 (C언어)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int deque[10001];
int count = 0;
int empty() {
if (count == 0) return 1;
else return 0;
}
void oneSpaceForward() { for (int i = 0; i < count; i++)deque[i] = deque[i + 1]; }
void oneSpaceBack() { for (int i = count; i >=0; i--)deque[i + 1] = deque[i]; }
void pushBack(int num) {
deque[count] = num;
count++;
}
void pushFront(int num) {
oneSpaceBack();
deque[0] = num;
count++;
}
int popFront() {
if (empty() == 1) return -1;
else {
count--;
return deque[0];
}
}
int popBack() {
if (empty() == 1) return -1;
else {
count--;
return deque[count];
}
}
int size() { return count; }
int front() {
if (empty() == 1) return -1;
else return deque[0];
}
int back() {
if (empty() == 1) return -1;
else return deque[count - 1];
}
int main(void) {
int N;
int num;
scanf("%d", &N);
char order[15];
for (int i = 0; i < N; i++)
{
scanf("%s", &order);
if (!strcmp(order, "push_back")) {
scanf("%d", &num);
pushBack(num);
}
else if (!strcmp(order, "push_front")) {
scanf("%d", &num);
pushFront(num);
}
else if (!strcmp(order, "pop_front")) {
printf("%d\n", popFront());
oneSpaceForward();
}
else if (!strcmp(order, "pop_back"))printf("%d\n", popBack());
else if (!strcmp(order, "size")) printf("%d\n", size());
else if (!strcmp(order, "empty")) printf("%d\n", empty());
else if (!strcmp(order, "front")) printf("%d\n", front());
else if (!strcmp(order, "back")) printf("%d\n", back());
else if (!strcmp(order, "check")) {
for (int i = 0; i < count; i++) {
printf("%d", deque[i]);
}
}
}
return 0;
}
│설명 (C언어)
keypoint 1- pop시에 빈칸 정리
void oneSpaceForward() { for (int i = 0; i < count; i++)deque[i] = deque[i + 1]; }
pop_front시에 배열의 앞부분을 pop 하며 배열에 0번째 원소가 비어있는 문제점을 위해 배열을 전체적으로 앞으로 한 칸 복사해 주는 함수를 통해 해결하였다.
void oneSpaceBack() { for (int i = count; i >=0; i--)deque[i + 1] = deque[i]; }
push_front 시에 배열의 앞부분에서 front 하며 배열에 0번째 원소에 새로운 값을 추가할 때 0번째 원소값이 지워지는 문제점을 위해 배열을 전체적으로 뒤로 한 칸 복사해 주는 함수를 통해 해결하였다.
keypoint 2- strcmp()
c언어에서 <string.h> 라이브러리 내에 포함되어 있는 strcmp() 함수를 사용하면 문자열을 비교할 수 있다.
strcmp() 함수의 정의는 다음과 같다.
int strcmp(const char* str1, const char* str2, size_t n);
strcmp함수는 str1 > str2 일 때 양수, str1 < str2 음수, str1==str2 인 경우 0을 리턴한다.
c언어의 기본적인 개념으로 문자열의 끝은 ￦0으로 이루어져 있다.
strcmp("abcd" , "ab")를 비교할 시 c와 ￦0를 비교하게 되어 양수인 1이 출력된다.
또한 c언어에서의 0이 아닌 정수인 경우 false를 의미하고 0인경우에는 true를 의미한다.
이를 활용하여 문자열 내에 원하는 문자열을 포함했을 때의 if문을 작성하면 다음과 같다.
if (!strcmp(order, "push_front"))
keypoint 3- empty함수 활용
int popFront() {
if (empty() == 1) return -1;
else {
count--;
return deque[0];
}
}
int popBack() {
if (empty() == 1) return -1;
else {
count--;
return deque[count];
}
}
int size() { return count; }
int front() {
if (empty() == 1) return -1;
else return deque[0];
}
int back() {
if (empty() == 1) return -1;
else return deque[count - 1];
}
pop(), front(), back() 함수들은 큐 자료구조가 비어있을 시 -1을 출력하는데, 이때 empty함수를 활용하면 더 직관적으로 활용할 수 있다.
전반적으로 10845번 큐 문제와 흡사한 구조이기에 코드와 구조를 재활용하여 풀이하였다.
[백준] 10845번 큐 ( 파이썬 / c언어)
│문제 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
yesdohyun.tistory.com
