https://programmers.co.kr/learn/courses/30/lessons/42587

큐를 사용하면 쉽게 풀 수 있는 문제이다.

스택과 큐에 대해 익숙하지 않거나 까먹었다면 먼저 이전 포스팅을 참고하여 이해하고 오는 것을 추천한다.

2021.12.04 - [알고리즘/알고리즘 강의] - [알고리즘] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

문제풀이

눈여겨봐야 할 점은 3가지다.

1. 대기목록에서 꺼낸 문서보다 중요도가 높은 문서가 대기목록에 남아있다면 꺼낸 문서를 다시 대기 목록에 넣는다.
2. 대기 목록에는 최대 100개의 문서가 있다.
3. 중요도는 숫자가 클수록 중요하다.

대기 목록인 priorities의 첫 원소를 차례대로 빼면서 나머지 원소 중 최대 중요도를 비교하여 뺀 문서보다 중요도 높은 문서가 있다면 뒤에 추가하는 형식으로 풀면 될 것이다.

이때 최대 100개의 문서밖에 없으므로 O(n)의 시간 복잡도를 가지는 max 함수로 최대 중요도를 비교하면 된다.

동시에 location에 해당하는 문서가 몇 번째에 출력되는지 묻는 문제이므로 원소를 pop 할 때마다 location을 감소시키고 음수가 되면 대기 목록의 마지막에 추가되었다고 생각하면 된다.

간단한 문제이므로 바로 전체 코드로 넘어가겠다.

def solution(priorities, location):
    answer = 0
    while len(priorities)>0:        #대기 목록에 문서가 있는 동안 반복
        temp=priorities.pop(0)      #첫 번째 문서 꺼내기
        if len(priorities)==0:      #껴낸 문서가 마지막 일때 종료
            answer+=1
        else:
            if temp>=max(priorities):   #꺼낸 문서의 중요도가 제일 높을 때
                if location==0:         #찾고자 하는 문서일 때 종료
                    answer+=1
                    break
                else:
                    location-=1
                    answer+=1
                        
            #꺼낸 문서보다 중요도가 높은 문서가 대기 목록에 존재할 때
            else:
                priorities.append(temp)
                location-=1
                if location<0:
                    location=len(priorities)-1
    return answer

3번째 줄은 대기 목록에 문서가 있는 동안 반복하기 위해 while문을 선언하였고  4번째 줄은 pop(0)을 통해 0번째 인덱스의 원소를 제거하며 반환한다.

또한 5번째 줄은 꺼낸 문서가 마지막 문서일 때 (더 이상 대기 목록에 문서가 없을 때) 고려할 조건이 없으므로 answer을 증가시킨 후 바로 종료한다.

8번째 줄의 if문은 max로 대기 목록의 중요도를 비교하여 더 높은 중요도가 없으면 출력하는 문서로 판단하고 location을 감소시킨다.

이때 location이 0이라면 꺼낸 문서가 찾는 문서이므로 answer을 증가시킨 뒤 break를 통해 반복문을 빠져나온다.

17번째 else는 대기 목록에 더 높은 중요도가 있을 때 뒤에 추가하는 구문으로 만약 location이 음수가 되면 대기 목록의 마지막에 추가했다는 의미이므로 현재 priorities 길이의 -1로 변경하면 된다.

이 문제는 Input Size가 상당히 작아서 굳이 시간 복잡도를 계산할 필요까진 없었던 것 같다.

조건만 잘 확인하고 구현한다면 충분히 쉽게 통과할 수 있을 것이다.

이 프린터 문제는 우선순위 큐란 알고리즘이다.

다만 우선순위 큐는 힙(Heap)이란 자료 구조를 사용하고 내부 구조에서 최댓값, 최솟값을 갱신하는데 O(logn)의 효율적인 시간 복잡도를 가진다.

파이썬은 Heapq란 모듈을 통해 쉽게 우선순위 큐를 구현 가능하며 해당 문제에서는 큐를 연습하기 위해 일부러 Input을 적게 주고 우선순위 큐의 결과를 나타낼 수 있도록 유도한 것 같다.

코테에서도 은근히 우선순위 큐를 사용하는 문제가 나오므로 우선순위 큐를 구현하는 힙에 대해서 포스팅하겠다.

설명

자료구조(Data Structure)를 공부할 때 가장 처음 접하는 것은 스택(Stack)과 큐(Queue)다.

그전에 자료구조란 Data를 효율적으로 저장하고 접근하여 사용하는 방법을 뜻한다.

적합한 상황에 적절한 자료구조를 사용하면 아주 효율적인 알고리즘을 사용할 수 있는 장점이 있다.

이번 시간에 가장 기본 중에 기본인 스택과 큐에 대해 알아보겠다.

스택 (Stack)

먼저 스택은 나중에 들어오는 Data가 먼저 나가는 LIFO(Last In First Out) 형태이다.

통에다가 블록을 넣고 빼는 방식을 연상하면 이해가 쉬울 것이다.

Data를 넣는 연산은 Push라고 한다.

반대로 Data를 빼는 연산은 Pop이라고 한다.

그림을 통해 쉽게 이해할 수 있듯이 나중에 들어간 Data가 먼저 나오고 먼저 들어간 Data가 나중에 나오는 자료구조를 스택이라고 표현한다.

만약 C 같이 다른 언어였다면 구조체를 선언하여 현재 얼마나 Data가 들어왔는지 판단하는 Top이란 변수를 통해 구현하겠지만 Python은 그럴 필요가 없다.

보통 라이브러리를 사용하는 경우를 제외하면 구현의 편의성을 위해 배열을 미리 선언(정적 할당)하고 잘못된 인덱스로 접근하는 Index Error를 방지하기 위해 Top이란 변수를 선언하여 오류를 방지한다.

또한 필요하다면 배열의 크기를 변경하는 복잡한 과정을 거쳐야 한다.

하지만 Python은 배열이 아닌 리스트를 지원하기 때문에 비교적 Data 추가 삭제에 대한 고민을 덜 수 있다.

큐 (Queue)

다음은 큐다.

큐는 먼저 들어온 Data가 먼저 나가는 FIFO(First In First Out) 형태이다.

즉, 차례대로 줄을 서서 기다리는 형태를 생각하면 된다.

큐에서 Data를 넣는 연산은 Enqueue라고 한다.

Data를 빼는 연산은 Dequeue라고 한다.

스택과는 다르게 먼저 들어간 Data가 먼저 빠지는 것을 확인할 수 있다.

구현

Python은 앞서 말한 대로 배열이 아닌 리스트를 지원하기 때문에 리스트와 관련되어 지원하는 함수들로 아주 쉽게 스택과 큐를 구현 가능하다.

여러 가지 함수들이 있지만 구현하는데 필요한 함수는 append()와 pop()이다.

각각 뒤에 원소를 추가하고 빼는 함수인데 pop(x)처럼 안에 인자를 넣으면 x번째 원소를 반환하고 제거한다는 의미이다.

이를 이용하여 x에 0을 넣으면 0번째 원소를 제거하므로 쉽게 큐를 구현할 수 있다.

다음은 앞서 설명한 과정을 그대로 구현한 전체 코드이다.

stack=[]    #스택 선언
print("현재 스택 :",stack)
stack.append(1)     # 1 추가
print("현재 스택 :",stack)
stack.append(2)     # 2 추가
print("현재 스택 :",stack)
stack.pop()         #끝 원소 하나 제거
print("현재 스택 :",stack)
stack.pop()         #끝 원소 하나 제거
print("현재 스택 :",stack, end="\n\n")

queue=[]    #큐 선언
print("현재 큐 :",queue)
queue.append(1)     # 1 추가
print("현재 큐 :",queue)
queue.append(2)     # 2 추가
print("현재 큐 :",queue)
queue.pop(0)         #첫 원소 하나 제거
print("현재 큐 :",queue)
queue.pop(0)         #첫 원소 하나 제거
print("현재 큐 :",queue)

복잡한 과정 없이 함수 두 개로 간단하게 구현하였으며 보통 그래프 탐색에서 스택은 깊이 우선 탐색(DFS), 큐는 너비 우선 탐색(BFS)에 자주 쓰인다.

따라서 코테준비를 위해 상당히 자주 사용할 문법이므로 알아야 한다.

데크 (Deque)

사실 큐는 구현 방법에 따라 다양한 이름이 있는데 가장 단순한 큐(Queue), 배열의 비효율성을 개선하기 위한 원형 큐(Circular Queue), 앞과 뒤 둘 다 Data를 넣고 뺄 수 있는 데크(Deque), 자료구조 중 하나인 힙(Heap)을 이용한 우선순위 큐(Priority Queue) 이런 식으로 장단점을 개선한 방식이 존재한다.

Python의 특성 상 원형 큐는 구현할 필요가 없고 우선순위 큐는 파이썬의 모듈 중 하나인 heapq를 사용하면 된다.

이번에 추가적으로 설명할 자료구조는 데크다.

데크 혹은 덱이라 부르는데 이 자료구조는 앞과 뒤에서 Enqueue와 Dequeue가 가능하다.

파이썬의 pop()은 O(1)의 시간 복잡도가 들지만 첫 번째 원소를 제거하기 위해 pop(0)을 사용하게 되면 끝에서부터 원소를 찾기에 O(n)의 시간 복잡도가 걸린다.

따라서 Input이 너무 큰 상황이라면 효율을 위해 데크를 사용하여 시간 복잡도를 줄일 수 있다.

주요 함수는 append(), appendleft(), pop(), popleft()이고 left가 붙으면 첫 번째에, 붙지 않으면 마지막에 적용된다.

데크 구현

다음은 데크의 연산 과정을 확인할 수 있는 전체 코드이다.

from collections import deque   #데크 모듈 선언
deque=deque()
print("현재 데크 :",deque)
deque.append(1)         #오른쪽에 1 추가
print("현재 데크 :",deque)
deque.appendleft(2)     #왼쪽에 2 추가
print("현재 데크 :",deque)
deque.popleft()         #첫 번째 원소 제거
print("현재 데크 :",deque)
deque.pop()             #끝 원소 제거
print("현재 데크 :",deque)

처음 보면 모듈 선언이 다소 어려울 수 있겠지만 익숙해진다면 그냥 리스트로 구현하는 것보다 시간 복잡도적으로 유리한 구현이 가능해진다.

스택과 큐를 연습할 수 있는 문제를 추천하며 마무리 짓겠다.

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

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