[백준] 10845번 큐 ( 파이썬 / c언어)

│문제

10845번: 큐

 

│풀이 (Python)

import sys

N=int(input())

stack=[]

for i in range(N):

    order=sys.stdin.readline().split()

    if "push" in order:

        stack.append(order[-1])

    elif "back" in order:

        if len(stack) == 0:

            print(-1)

        else: print(stack[len(stack)-1])

    elif "front" in order:

        if len(stack) == 0:

            print(-1)

        else: print(stack[0])

    elif "size" in order:

        print(len(stack))

    elif "empty" in order:

        if len(stack) == 0:

            print(1)

        else: print(0)

    elif "pop" in order:

        if len(stack) == 0:

            print(-1)

        else:

            print(stack[0])

            stack.pop(0)

 

│설명 (Python)

 

큐는 선입선출(FIFO)인 자료구조이다. 큐는 push와 pop기능을 활용하는 대표적인 자료구조 중 하나이다.

push와 pop의 기능은 다음과 같다.

push: 리스트에 append()를 통해 원소를 저장한다.

pop: 리스트에서 pop()을 통해 원소를 밖으로 꺼낸다.

 

keypoint 1- pop(0)

파이썬에서 기본적으로 제공하는 pop함수는 원소를 제거만하는것이 아닌 리스트의 전체 길이를 앞으로 한 칸씩 축소시킨다. 

[1, 2, 3, 4, 5]

pop(0)

위의 리스트에서 pop(0)을 하였을 때 [ , 2, 3, 4, 5] 와 같이 변형 되지 않는다.[ 2, 3, 4, 5]  0번 원소가 제거된 후 리스트 전체 인덱스가 앞으로 1칸 씩 줄어들게 된다.

pop함수를 드래그후 마우스 우클릭에 정의로 이동하여 확인해보면,

pop()함수 작동시 인덱스가 줄어드는 내용에 관한 정의를 확인할 수 있다.

 

 

keypoint 2- sys.stdin.readline()

시간초과 문제를 해결하기 위해 스택문제와 같이 input()이 아닌 sys.stdin.readline()을 활용하여야 한다.

pop()함수 작동시 인덱스가 줄어드는 내용에 관한 정의를 확인할 수 있다.

입력 속도 sys.stdin.readline() > input()

 

 

│풀이 (C언어)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <string.h>

int queue[10001];

int count = 0;

int empty() {

    if (count == 0) return 1;

    else return 0;

}

void push(int num) {

    queue[count] = num;

    count++;

}

int pop() {

    if (empty() == 1) return -1;

    else {

        count--;

        return queue[0];

    }

}

int size() {return count;}

int front() {

    if (empty() == 1) return -1;

    else return queue[0];

}

int back() {

    if (empty() == 1) return -1;

    else return queue[count-1];

}

void oneSpaceForward() {for (int i = 0; i < count; i++)queue[i] = queue[i + 1];}

int main(void) {

    int N;

    int num;

    scanf("%d", &N);

    char order[10];

    for (int i = 0; i < N; i++)

    {

        scanf("%s", &order);

        if (!strcmp(order, "push")) {

            scanf("%d", &num);

            push(num);

        }

        else if (!strcmp(order, "pop")) {

            printf("%d\n", pop());

            oneSpaceForward();

        }

        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());

    }

    return 0;

}

 

│설명 (C언어)

int queue[10001];

int count = 0;

배열과 top을 가르키는 count변수로 큐 자료구조를 구성하였다.

c언어는 python의 pop()과 같은 역할을 하는 함수가 없으므로 배열에서 0번 원소를 출력후 0번 원소를 삭제하고,

 배열을 앞으로  한 칸 당겼다.

 

큐 문제를 c언어로 풀이하기에는 대표적으로 3가지정도 있는데,

1.구조체를 활용하여 front와 rear를 설정 후 풀이

2.배열에서 front와 rear를 설정하여 풀이

3.배열에서 pop시에 전체적으로 한칸 앞으로 당기기

3번인 경우 앞으로 한 칸 당기는 함수에서 시간복잡도와 공간복잡도가 증가하지만, 풀이에 제일 직관적이다.

 

void oneSpaceForward() {for (int i = 0; i < count; i++)queue[i] = queue[i + 1];}

필자는 위의 함수를 통해 3번 방법으로 풀이하였다.

 

keypoint 1- 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"))

 

keypoint 2- empty함수 활용

int front() {

    if (empty() == 1) return -1;

    else return queue[0];

}

int back() {

    if (empty() == 1) return -1;

    else return queue[count-1];

}

pop(), front(), back() 함수들은 큐 자료구조가 비어있을 시 -1을 출력하는데, 이때 empty함수를 활용하면 더 직관적으로 활용할 수 있다.