[Java] 백준 1021번 회전하는 큐

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

1021번: 회전하는 큐

 

핵심

양방향 순환큐에서 주어진 원소들을 순서대로 뽑아낼 때,

2개의 연산(왼쪽이동, 오른쪽이동)에 대한 최솟값을 어떻게 구할 것인가?

 

→ 왼쪽이동을 기준으로 카운트를 세고

    Math.min(count, q.size() - count) 로 최소 이동횟수를 구한다.

 

 

 

포인트

•  2개의 큐

   1 ~ N의 원소를 가진 큐(q) 와, 지민이가 뽑아내려는 원소를 담은 큐(x) 

 

•  왼쪽이동연산 구현 (원소 뒤로 보내기)

   큐 x의 모든 원소를 순서대로 꺼내며 x의 원소와 큐 q의 원소가 같지 않을때까지

   poll() 메소드와 add() 메소드를 이용해 q의 원소를  끝으로 보낸다.

 

•  이동연산의 최솟값

   왼쪽이동을 기준으로 카운팅하고,

   그 카운팅과 q.size - count 를 비교해서 더 작은 쪽이 최솟값이다.

 

•  일치하는 원소 뽑기

   큐 x의 원소와 q의 원소가 같을때 q.poll() 로 원소를 뽑아줘야 다음 이동에 영향이 없다.

 

//큐의 크기 N 
//뽑아내려고 하는 수의 개수 M
//수의 위치 M개

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new LinkedList<>();
        Queue<Integer> x = new LinkedList<>();
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int ans = 0;
        
        for(int i = 1; i <= N; i++)
            q.add(i); 
            
        for(int i = 0; i < M; i++) 
            x.add(sc.nextInt());
        
        while(!x.isEmpty()) {
            int num = x.poll();  
            int count = 0;         
            while(num != q.peek()) {
                int front = q.poll();
                q.add(front);
                count++;
            }
            ans += Math.min(count, q.size() - count);
            q.poll();
        }
        System.out.println(ans);
    }
}

 

 

 

 

기억하자

왼쪽, 오른쪽 이동	큐에서 왼쪽, 오른쪽 이동은 원소를 poll 하고 다시 add 해서 옮김
공백 입력값	Scanner를 이용해도 공백 상관없이 sc.nextInt() 등으로 입력값을 가져올 수 있음

 

 

 

 

자주 까먹는 메소드 (문제와 무관)

✅   Map.getOrDefault(Object key, V defaultValue) 

key	찾을 키 값
defaultValue	키가 맵에 없을 경우 반환할 기본값
(예시) map.getOrDefault(c,0) + v	키 c가 맵에 없을경우 값을 0으로 설정하고 그게 아니라면 v를 더함