Queue

백준 회전하는 큐

• 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

interface Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());

    Deque<Integer> dq = new LinkedList<>();
    for (int i = 1; i <= n; i++) {
      dq.add(i);
    }

    int cnt = 0;

    for (int i = 0; i < m; i++) {
      int left = 0;
      int right = 0;
      int target = Integer.parseInt(st.nextToken());

      for (int j = 0; j < dq.size(); j++) {
        if (dq.toArray()[j].equals(target)) {
          left = j;
          right = n - left;

          break;
        }
      }

      if (left < right) {
        for (int j = 0; j < left; j++) {
          dq.addLast(dq.pollFirst());
          cnt++;
        }
      } else {
        for (int j = 0; j < right; j++) {
          dq.addFirst(dq.pollLast());
          cnt++;
        }
      }

      dq.pollFirst();
      n--;

    }

    System.out.println(cnt);
    }
}

프로그래머스

• 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        Queue<Integer> q = new LinkedList<>();
    ArrayList<Integer> l = new ArrayList<>();
    for (int i = 0; i < progresses.length; i++) {
      int check = (100 - progresses[i]) % speeds[i];
      int remain = (100 - progresses[i]) / speeds[i];
      if (check == 0)
        q.add(remain);
      else
        q.add(remain + 1);
    }

    int cnt = 1;

    while (!q.isEmpty()) {
      int idx = 0;
      int offset = 1;
      while (idx + offset < q.size() && ((int) q.toArray()[idx] >= (int) q.toArray()[idx + offset])) {
        cnt++;
        offset++;
      }

      for (int j = 0; j < cnt; j++) {
        q.poll();
      }
      l.add(cnt);
      cnt = 1;

    }
        answer = l.stream().mapToInt(i -> i).toArray();
        return answer;
    }
}

TIL

• 큐를 linkedlist로 만들어서 pop()아니고 poll()