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

3개의 배열을 이용해 풀었습니다.

answer는 프린터가 된 순서가 담길 배열입니다.

array는 매개변수로 입력받는 priorities의 배열이 큐로 변환될 배열입니다.

index는 array의 각 숫자들의 원래 인덱스를 저장할 배열입니다.

풀이 코드는 아래와 같은데 코드를 하나씩 풀어보면서 설명해보겠습니다.

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        int[] answer = new int[priorities.length];
        Deque<Integer> array = new ArrayDeque<Integer>();
        Deque<Integer> index = new ArrayDeque<Integer>();
        
        for(int i = 0; i < priorities.length; i++ ){
            array.offer(priorities[i]);
            index.offer(i);
        }
        int sum = 1;
        while(array.peek() != null){
            int max = Collections.max(array);
            if(array.peek() < max){
                array.offer(array.poll());
                index.offer(index.poll());
            }else{
                array.poll();
                answer[index.poll()] = sum;
                sum += 1;
            }
        }
        
        return answer[location];
    }
}

초기값을 array와 index에 넣으면 위와 같습니다.

sum값은 프린터 되는 순서를 세어줄 변수입니다.

max는 array에서 가장 큰 값이 담기게 됩니다.

우선 array 배열의 첫 번째 값과 max값을 비교해서 첫 번째 값이 작을 경우

첫 번째 값을 배열 맨 뒤에 추가하고 인덱스의 첫 번째 값도 맨 뒤에 추가해줍니다.

이것을 반복하다가 array의 가장 큰 값과 만나면 가장 큰 값을 array에서 제거합니다.

그리고 answer의 해당 index에 순서 값인 sum을 넣어 주고 sum을 + 1 해줍니다.

이렇게 반복해서 array의 숫자가 사라질 때까지 반복하면 

프린터 순서가 담긴 answer 배열이 생성됩니다.

거기서 location으로 들어온 위치의 값을 반환하면 됩니다.

이번 주 스터디에서는 자료구조 중 스택과 큐에 대해 공부하고 문제를 풀어보는 시간을 가졌습니다.

전에도 스택과 큐에 대해서 공부해봤기 때문에 구조적인 측면에서 이해는 문제가 없었습니다.

하지만 파이썬으로 구현했던 거라 자바로 구현하려고 하니 '어떤 클래스를 사용하고 어떤 메서드를 사용하지?'라는 생각이 들었습니다.

그래서 이걸 간단히 정리해 보려고 합니다.

스택과 큐의 자료구조와 메서드에 대해 정리하겠습니다.

스택(Stack)

스택은 LIFO(Last In First Out)의 특징을 가지고 있습니다.

이건 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 말합니다.

다르게 표현하면 가장 먼저 들어간 데이터가 가장 마지막으로 나오는 것을 뜻하기도 합니다.

재귀적인 함수, 알고리즘에 사용됩니다.

데이터를 삽입 및 삭제에 O(1), 탐색에 O(n) 시간이 걸립니다.

자바에서는 Stack 클래스를 구현하여 제공합니다.

Stack 클래스 메서드는 아래와 같습니다.

Stack<Integer> st = new Stack<Integer>();

큐(Queue)

큐는 FIFO(First In First Out)의 특성을 가지고 있습니다.

이는 먼저 집어넣은 데이터가 먼저 나오는 성질을 말합니다.

때문에 데이터를 집어넣으면 뒤부터 순차적으로 생성되고 

뺄 때는 가장 처음 데이터부터 나오게 됩니다.

삽입 및 삭제에 O(1), 탐색에 O(n)의 시간이 걸립니다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬

너비 우선 탐색(BFS), 캐시 등에 사용됩니다.

자바에서 큐의 경우에는 클래스가 아닌 인터페이스를 제공합니다.

물론 구현해 놓은 클래스도 있기 때문에 그중 하나를 사용하면 됩니다.

예시로 ArrayDeque, ConcurrentLinkedDeque, LinkedList가 있습니다.

Deque의 경우에는 앞뒤로 데이터를 넣고 빼는 메서드를 가지고 있습니다.

메서드는 아래와 같습니다.

위 세 개와 아래 세 개의 메서드는 같은 기능을 하지만 오류를 반환하고 하지 않는 차이가 있습니다.

Queue<Integer> q = new LinkedList<Integer>()

2022.03.08

백준 1966 프린터 큐

#1966 프린터 큐
from collections import deque
# 테스트 케이스  T
T = int(input())

for i in range(T):
  N,M = map(int, input().split())
  
  # 인덱스의 변화를 보여줄 큐, idx를 하나 만든후 인덱스를 저장한다.
  idx = deque()
  for j in range(N):
    idx.append(j)
    
  # arr에 우선순위로 주어진 입력값을 저장한다.
  arr = deque()
  array = list(map(int, input().split()))
  for j in array:
    arr.append(j)
  
  # num은 queue에서 값이 pop될 때마다 +1 해줘 M번째 값이 몇 번째로 출력되는지 계산한다.
  num = 1
  while True:
    if M == idx[0] and arr[0] == max(arr):
      print(num)
      break
    else:
      if max(arr) == arr[0]:
        arr.popleft()
        idx.popleft()
        num += 1
      else:
        arr.append(arr.popleft())
        idx.append(idx.popleft())

그동안 고민하면서 못 풀었던 문제를 드디어 풀었다.

처음에는 큐 하나만 이용해서 풀려고 하다가 인덱스도 큐로 만들어서 변화를 주어야겠구나 생각을 하게 되었고

또 거기서 한동안 못풀다가 while문에서 멈추는 조건을 잘 못주고 있었다는 걸 깨닫고 풀 수 있었다.

2022.02.08 요세푸스 문제

#11866 요세푸스 문제
from collections import deque

N, K = map(int, input().split())
arr = deque()
for i in range(1,N+1):
    arr.append(i)
result = []

for i in range(N):
    for j in range(K-1):
        arr.append(arr.popleft())
    result.append(arr.popleft())

print('<', end = '')
print(*result,sep=', ',end='')
print('>')

수학적으로 풀어 보려다가 큐로 풀면 될 것 같아서 큐로 풀었다.

입력받은 K-1개만큼 리스트의 뒤로 보내주고 K번째 것만 새로운 리스트인 result에 담아준다.

그리고 result를 출력해주면 끝

2022.02.07

백준 2164 카드 2

#2164 카드2

N = int(input())
arr = [i for i in range(1,N+1)]

while len(arr) != 1:
    s = arr[1]
    del arr[0]
    arr.append(s)
    del arr[1]

print(arr[0])

#2164 카드2
from collections import deque

N = int(input())
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while len(queue) != 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

처음에 위 코드로 풀었다가 시간 초과가 떴다.

시간 복잡도는 while문 처음 시작할 때까지는 같은 거 같은데

무엇에서 차이나는 걸까

2022.01.27

백준 10845 큐

# 10845 큐
import collections 
import sys

N = int(sys.stdin.readline())
queue = collections.deque()

for i in range(N):
    q = sys.stdin.readline().split()
    if q[0] == 'push':
        queue.append(int(q[1]))
    elif q[0] == 'pop':
        try:
            print(queue.popleft())
        except:
            print(-1)
    elif q[0] == 'size':
        print(len(queue))
    elif q[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)
    elif q[0] == 'front':
        if not queue:
            print(-1)
        else:
            print(queue[0])
    elif q[0] == 'back':
        if not queue:
            print(-1)
        else:
            print(queue[-1])

조건문만 잘 만들어내면 되는 문제라 그리 어렵지는 않았는데

시간 초과가 뜨길래 sys를 사용했다.

#1158
from collections import deque

N, K = map(int, input().split())

R = []
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while queue:
    for i in range(K-1):
        queue.append(queue.popleft())
    R.append(queue.popleft())
    
print('<', end = '')
print(*R, sep = ', ', end = '')
print('>')