백준 문제 중 10845번, 큐, ‘큐’

January 31, 2022 8 minute read

백준 문제 중 10845번

https://www.acmicpc.net/problem/10845

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

deque는 double eneded queue으로 양쪽 끝 모두 인큐 딬 가 가능한 자료형이다.

from collections import deque
from typing import Any

class Queue:

    def __init__(self)->None:
        self.que = deque()

    def is_empty(self)->bool:
        return len(self.que)<=0

    def push(self,x:int)->None:
         # que의 오른쪽 x 인큐
        self.que.append(x)

    def pop(self)->Any:
        if self.is_empty():
            return -1
        else:
             # popleft로 que의 head 디큐
            return self.que.popleft()

    def size(self)->int:
        return len(self.que)

    def empty(self)->int:
        if self.is_empty():
            return 1
        else:
            return 0

    def front(self)->int:
        if self.is_empty():
            return -1
        else:
             # que의 제일 앞 인덱스의 원소 반환
            return self.que[0]

    def back(self)->int:
        if self.is_empty():
            return -1
        else:
             # que의 제일 끝 인덱스의 원소 반환
            return self.que[self.size()-1]

n = int(input())
x = Queue()
ans = []

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'push': x.push(int(cmd[1]))
    elif cmd[0] == 'pop': ans.append(x.pop())
    elif cmd[0] == 'size': ans.append(x.size())
    elif cmd[0] == 'empty': ans.append(x.empty())
    elif cmd[0] == 'front': ans.append(x.front())
    elif cmd[0] == 'back': ans.append(x.back())

for an in ans: print(an)

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front
1
2
2
0
1
2
-1
0
1
-1
0
3

보충

링 버퍼로 구현

링 버퍼는 길이가 고정된 배열을 선언한뒤 접근하려는 인덱스가 배열의 크기보다 크다면 다시 0으로 돌아가 시작하는 형태의 배열이다. 처음과 끝이 이어져 있어 링과 같은 모양이 된다.

from collections import deque
from typing import Any

class Queue:

    def __init__(self,capacity:int)->None:
      
         # 링버퍼 que 크기를 설정할 capacirt   
        self.capacity = capacity
        self.que = [None]*capacity

         # que의 머리에 접근할 인덱스 f선언
        self.f = 0
         # que의 꼬리에 접근할 인덱스 b선언
        self.b = 0
         # que가 가득찼는지와 원소 개수를 판단할 no 선언
        self.no = 0

    def is_empty(self)->bool:
        return self.no<=0

    def push(self,x:int)->None:
        
         # que가 가득 찼다면 push 실패    
        if self.no>=self.capacity:
            return False

         # que가 비어있고 b가 que의 크기보다 크거나 같다면 0으로 돌아감
        if self.b>=self.capacity:
            self.b=0

         # que[self.b]에 x를 할당하고 b는 다음 원소를 가르킴
        self.que[self.b]=x
        self.b+=1
        self.no+=1

    def pop(self)->Any:

        if self.is_empty():
            return -1
        else:
             # f가 que의 크기보다 크거나 같다면 0으로 돌아감
            if self.f>=self.capacity:
                self.f=0
            idx=self.f
            self.f+=1
            self.no-=1
            return self.que[idx]

    def size(self)->int:
        return self.no

    def empty(self)->int:
        if self.is_empty():
            return 1
        else:
            return 0

    def front(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[self.f]

    def back(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[self.b-1]

x=Queue(12)

x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
print(x.pop())
print(x.pop())
print(x.pop())
print(x.size())
print(x.empty())
print(x.front())
print(x.back())

연결리스트로 구현

LinkedList-(1) SingleLinkedList

from typing import Any,Type

# 노드 클래스 선언
class Node:
     
    def __init__(self,data:Any,next:Node=None):

        self.data = data
        self.next = next

# 싱글 링크드리스트 클래스 선언
class SingleLinkedList:

     # 시작 head, 현재 cur, 갯수 no 선언
    def __init__(self):

        self.head = None
        self.cur = None
        self.no = 0


     # dunder 함수로 len구현
    def __len__(self):

        return self.no


     # 원하는 데이터를 찾는 함수
    def search(self,data:Any)->int:

         # data의 인덱스를 나타낼 변수
        cnt = 0
        
         # head 부터 시작해서 노드가 none이 될때까지 next
        p = self.head
        while p is not None:

            # 스캔중 data 발견시 return cnt 
            if p.data == data:
                self.cur = p    
                return cnt
            p = p.next
            cnt+=1
   
         # 검색 실패시 return -1
        return -1


     # 머리에 노드추가 함수
    def add_first(self,data:Any)->None:

         # 기존의 self.head를 next로 data를 data로 갖는 노드 추가
         # cur, no 업데이트  
        self.head = self.cur = Node(data,self.head)
        self.no+=1


     # 꼬리 노드추가 함수 
    def add_last(self,data:Any)->None:

         # 리스트가 비었다면 머리추가와 동일
        if self.head is None:
            self.add_first(data)

        else:

             # p.next가 None 즉 마지막 노드까지 스캔
            p = self.head
            while p.next is not None:
                p = p.next

             # 마지막노드 p의 next에 data를 data로 갖는 노드 추가
             # cur, no 업데이트
            p.next = self.cur = Node(data)
            self.no+=1


     # 머리노드 삭제 함수
    def remove_first(self)->bool:

         # 리스트가 비었다면 삭제 실패 False 반환
        if self.head is None:
            return False

         # head가 None이 아니라면 head를 삭제
         # cur, no 업데이트 후 True 반환            
        else:
            self.head = self.cur = self.head.next
            self.no-=1
            return True


     # 꼬리노드 삭제 함수
    def remove_last(self)->bool:

         # 리스트가 비었다면 false 반환
        if self.head is None:
            return False

         # p.next가 none 즉 마지막 노드까지 스캔
         # 단. pre에 이전 p를 저장하며 진행
        else:
            p = self.head
            pre = self.head
            while p.next is not None:
                pre = p
                p = p.next
    
             # 마지막 노드 p의 전 노드 pre의 next를 None으로 업데이트
            pre.next = None
            self.cur = pre
            self.no-=1
            return True

     # 노드x를 삭제하는 함수
    def remove(self,x:Node)->None:
  
         # 리스트가 비었다면 false 반환  
        if self.head is None:
            return False
        else:
            p = self.head

             # p의 next와 x가 일치할때 까지 진행
            while p.next is not x:
                p = p.next

                 # 마지막 노드까지 없다면 false 반환
                if p is None:
                    return False

             # p의 next가 x이므로 p.next에 x의 next 대입
            p.next = x.next
            self.cur = p
            self.no-=1

    def remove_cur_node(self)->None:
        self.remove(self.cur)

    def print_cur_node(self)->None:

        if self.cur is None: print('-1')
        else: print(self.cur.data)

    def print(self)->None:
       
        p=self.head
        while p is not None:
            print(p.data)
            p=p.next

    def clear(self)->None:

        while self.head is not None:
            self.remove_first()
        self.cur = None
        self.no


class Queue(SingleLinkedList):

    def push(self,data)->None:
        self.add_last(data)

    def pop(self)->None:
        self.cur = self.head
        self.print_cur_node()
        self.remove_first()

    def size(self)->None:
        print(self.no)

    def empty(self)->None:
        print(1 if self.no<=0 else 0)

    def front(self)->None:
        self.cur = self.head
        self.print_cur_node()

    def back(self)->None:

        if self.head is None:
            return print(-1)
        else:
            p=self.head
            while p.next is not None:
                p=p.next
            print(p.data)

x=Queue()

x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
x.pop()
x.pop()
x.pop()
x.size()
x.empty()
x.front()
x.back()

성능비교

1.덱

%%time
from collections import deque
from typing import Any

class Queue:

    def __init__(self)->None:
        self.que = deque()

    def is_empty(self)->bool:
        return len(self.que)<=0

    def push(self,x:int)->None:
        self.que.append(x)

    def pop(self)->Any:
        if self.is_empty():
            return -1
        else:
            return self.que.popleft()

    def size(self)->int:
        return len(self.que)

    def empty(self)->int:
        if self.is_empty():
            return 1
        else:
            return 0

    def front(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[0]

    def back(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[self.size()-1]

x=Queue()
x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
print(x.pop())
print(x.pop())
print(x.pop())
print(x.size())
print(x.empty())
print(x.front())
print(x.back())

1
2
3
2
0
4
5
CPU times: user 1.74 ms, sys: 0 ns, total: 1.74 ms
Wall time: 1.75 ms

링버퍼

%%time
from collections import deque
from typing import Any

class Queue:

    def __init__(self,capacity:int)->None:
      

         # 링버퍼 que 크기를 설정할 capacirt   
        self.capacity = capacity
        self.que = [None]*capacity


         # que의 머리에 접근할 인덱스 f선언
        self.f = 0

         # que의 꼬리에 접근할 인덱스 b선언
        self.b = 0

         # que가 가득찼는지와 원소 개수를 판단할 no 선언
        self.no = 0

    def is_empty(self)->bool:
        return self.no<=0

    def push(self,x:int)->None:
        

         # que가 가득 찼다면 push 실패    
        if self.no>=self.capacity:
            return False


         # que가 비어있고 b가 que의 크기보다 크거나 같다면 0으로 돌아감
        if self.b>=self.capacity:
            self.b=0

         # que[self.b]에 x를 할당하고 b는 다음 원소를 가르킴
        self.que[self.b]=x
        self.b+=1
        self.no+=1

    def pop(self)->Any:

        if self.is_empty():
            return -1
        else:

             # f가 que의 크기보다 크거나 같다면 0으로 돌아감
            if self.f>=self.capacity:
                self.f=0
            idx=self.f
            self.f+=1
            self.no-=1
            return self.que[idx]

    def size(self)->int:
        return self.no

    def empty(self)->int:
        if self.is_empty():
            return 1
        else:
            return 0

    def front(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[self.f]

    def back(self)->int:
        if self.is_empty():
            return -1
        else:
            return self.que[self.b-1]

x=Queue(12)

x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
print(x.pop())
print(x.pop())
print(x.pop())
print(x.size())
print(x.empty())
print(x.front())
print(x.back())

1
2
3
2
0
4
5
CPU times: user 1.83 ms, sys: 0 ns, total: 1.83 ms
Wall time: 1.83 ms

연결리스트

%%time
from typing import Any,Type

# 노드 클래스 선언
class Node:
     
    def __init__(self,data:Any,next:Node=None):

        self.data = data
        self.next = next

# 싱글 링크드리스트 클래스 선언
class SingleLinkedList:

     # 시작 head, 현재 cur, 갯수 no 선언
    def __init__(self):

        self.head = None
        self.cur = None
        self.no = 0


     # dunder 함수로 len구현
    def __len__(self):

        return self.no


     # 원하는 데이터를 찾는 함수
    def search(self,data:Any)->int:

         # data의 인덱스를 나타낼 변수
        cnt = 0
        
         # head 부터 시작해서 노드가 none이 될때까지 next
        p = self.head
        while p is not None:

            # 스캔중 data 발견시 return cnt 
            if p.data == data:
                self.cur = p    
                return cnt
            p = p.next
            cnt+=1
   
         # 검색 실패시 return -1
        return -1


     # 머리에 노드추가 함수
    def add_first(self,data:Any)->None:

         # 기존의 self.head를 next로 data를 data로 갖는 노드 추가
         # cur, no 업데이트  
        self.head = self.cur = Node(data,self.head)
        self.no+=1


     # 꼬리 노드추가 함수 
    def add_last(self,data:Any)->None:

         # 리스트가 비었다면 머리추가와 동일
        if self.head is None:
            self.add_first(data)

        else:

             # p.next가 None 즉 마지막 노드까지 스캔
            p = self.head
            while p.next is not None:
                p = p.next

             # 마지막노드 p의 next에 data를 data로 갖는 노드 추가
             # cur, no 업데이트
            p.next = self.cur = Node(data)
            self.no+=1


     # 머리노드 삭제 함수
    def remove_first(self)->bool:

         # 리스트가 비었다면 삭제 실패 False 반환
        if self.head is None:
            return False

         # head가 None이 아니라면 head를 삭제
         # cur, no 업데이트 후 True 반환            
        else:
            self.head = self.cur = self.head.next
            self.no-=1
            return True


     # 꼬리노드 삭제 함수
    def remove_last(self)->bool:

         # 리스트가 비었다면 false 반환
        if self.head is None:
            return False

         # p.next가 none 즉 마지막 노드까지 스캔
         # 단. pre에 이전 p를 저장하며 진행
        else:
            p = self.head
            pre = self.head
            while p.next is not None:
                pre = p
                p = p.next
    
             # 마지막 노드 p의 전 노드 pre의 next를 None으로 업데이트
            pre.next = None
            self.cur = pre
            self.no-=1
            return True

     # 노드x를 삭제하는 함수
    def remove(self,x:Node)->None:
  
         # 리스트가 비었다면 false 반환  
        if self.head is None:
            return False
        else:
            p = self.head

             # p의 next와 x가 일치할때 까지 진행
            while p.next is not x:
                p = p.next

                 # 마지막 노드까지 없다면 false 반환
                if p is None:
                    return False

             # p의 next가 x이므로 p.next에 x의 next 대입
            p.next = x.next
            self.cur = p
            self.no-=1

    def remove_cur_node(self)->None:
        self.remove(self.cur)

    def print_cur_node(self)->None:

        if self.cur is None: print('-1')
        else: print(self.cur.data)

    def print(self)->None:
       
        p=self.head
        while p is not None:
            print(p.data)
            p=p.next

    def clear(self)->None:

        while self.head is not None:
            self.remove_first()
        self.cur = None
        self.no


class Queue(SingleLinkedList):

    def push(self,data)->None:
        self.add_last(data)

    def pop(self)->None:
        self.cur = self.head
        self.print_cur_node()
        self.remove_first()

    def size(self)->None:
        print(self.no)

    def empty(self)->None:
        print(1 if self.no<=0 else 0)

    def front(self)->None:
        self.cur = self.head
        self.print_cur_node()

    def back(self)->None:

        if self.head is None:
            return print(-1)
        else:
            p=self.head
            while p.next is not None:
                p=p.next
            print(p.data)

x=Queue()

x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
x.pop()
x.pop()
x.pop()
x.size()
x.empty()
x.front()
x.back()

1
2
3
2
0
4
5
CPU times: user 1.87 ms, sys: 0 ns, total: 1.87 ms
Wall time: 1.87 ms

결론

성능은 그냥 거기서 거기였다. 그냥 제일 구현하기 편한 deque쓰는게 생산성에서 가장 좋은것 같다.

Share on

Twitter Facebook LinkedIn

Kim Boseong

백준 문제 중 10845번, 큐, ‘큐’

백준 문제 중 10845번

문제

입력

출력

풀이

보충

성능비교

결론

Share on

Leave a comment

You may also enjoy

Pandas와 클라우드 DB 데이터 읽기 속도 비교

numpy 자료형과 Pydantic에 의해 발생했던 버그

Variational AutoEncoder 정리 - (2) Variational AutoEncoder

부스트캠프 AI 13주차(Day-89) Movie Recommendation - (3) 베이스라인 분석