백준 - 1021번 회전하는 큐 (실버 3)

처음엔 deque을 사용해서 풀려고 했지만

deque에는 해당 원소의 인덱스를 반환하는 메소드가 없는 듯했다.

꺼내려는 숫자가 어느 인덱스에 있냐에 따라

앞으로 회전시킬지 뒤로 회전시킬지를 정해야 했기 때문에 인덱스 반환 메소드가 필요했다.

그래서 결국 List를 사용했다.

 

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] str=br.readLine().split(" ");
        int N=Integer.parseInt(str[0]);
        int M=Integer.parseInt(str[1]);
        List <Integer> deq=new LinkedList<>();

        for(int i=1;i<=N;i++){
            deq.add(i);
        }

        int cnt=0;
        int index=0;
        int result=0;
        String[] s=br.readLine().split(" ");


        while(index<M){
            int num=Integer.parseInt(s[index]);
            if(deq.size()/2>=deq.indexOf(num)){ 
            //꺼내려는 숫자가 덱의 크기/2보다 작거나 같다면 뒤로 회전
                while(!deq.isEmpty()){
                    result=deq.remove(0);
                    if(num==result)
                        break;
                    else {
                        deq.add(result);
                        cnt++;
                    }
                }
            }
            else{ //아니라면 앞으로 회전
                while(!deq.isEmpty()){
                    int size=deq.size();
                    result=deq.remove(size-1);
                    if(num==result){
                        cnt++; //회전시킨다음에 빼야 하나 생략하고 cnt 증가
                        break;
                    }
                    else{
                        deq.add(0,result); // 맨 앞에 넣기
                        cnt++;
                    }
                }
            }
            index++;

        }


        bw.write(cnt+"");
        bw.flush();
        bw.close();
    }
}

 

 

1. 리스트에서 해당 원소의 인덱스 반환 메소드

: list.indexOf(num);

 

 

2. 리스트에서 원하는 위치에 원소 삽입

: list.add(0, result);

 

 

3. 리스트의 원소들의 상황을 지켜보기 위해 리스트를 출력해 보았다.

리스트 통째로 출력이 가능하더라.

System.out.println(deq);

 

---

LinkedList를 사용해도 됨.

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] str=br.readLine().split(" ");
        int N=Integer.parseInt(str[0]);
        int M=Integer.parseInt(str[1]);
        LinkedList <Integer> deq=new LinkedList<>();

        for(int i=1;i<=N;i++){
            deq.add(i);
        }

        int cnt=0;
        int index=0;
        int result=0;
        String[] s=br.readLine().split(" ");


        while(index<M){
            int num=Integer.parseInt(s[index]);
            if(deq.size()/2>=deq.indexOf(num)){
                while(!deq.isEmpty()){
                    
                    result=deq.remove(0);
                    if(num==result)
                        break;
                    else {
                        deq.add(result);
                        cnt++;
                    }
                }
            }
            else{
                while(!deq.isEmpty()){
                    
                    
                    result=deq.removeLast();
                    if(num==result){
                        cnt++;
                        break;
                    }
                    else{
                        deq.addFirst(result); // 맨 앞에 넣기
                        cnt++;
                    }
                }
            }
            index++;

        }


        bw.write(cnt+"");
        bw.flush();
        bw.close();
    }
}