백준자바 1021 알고리즘 '회전하는큐' 문제풀이

오늘도 상쾌한 마음으로 백준 문제를 풀었습니다.

링크드리스트(Linked List) 문제를 배열없이 Linked List를 이용해 풀었습니다.

코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 1021번 문제 링크

More info: 회전하는 큐





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘

/*
Made by SONG KIM
2020-10-02
 */

import java.util.Scanner;

public class Main {

    public static class Node {
        int data;
        Node next;
        Node previous;

        public void displayNode(){
            System.out.println("{ " + data + " }" );
        }
    }

    public static class CustomLinkedList {
        Node first;
        Node last;

        public CustomLinkedList() {
            this.first = null;
            this.last = null;
        }

        public void InsertFirst(int data){
            Node newNode = new Node();
            newNode.data = data;

            if(IsEmpty())
            {
                last = newNode;
            }else {
                first.previous = newNode;
            }
            newNode.next = first;
            this.first = newNode;
        }

        public void InsertLast(int data){
            Node newNode = new Node();
            newNode.data = data;

            if(IsEmpty())
            {
                first = newNode;
            }else {
                last.next = newNode;
            }
            newNode.previous = last;
            this.last = newNode;
        }

        public Node DeleteFirstNode(){
            Node temp = first;
            if(first.next == null){
                last = null;
            }else {
                first.next.previous = null;
            }
            first = first.next;
            return temp;

        }

        public boolean IsEmpty(){
            return (first == null);
        }

        //앞쪽 부터 몇번 리스트를 움직여야 해당 숫자를 없애는지 체크크
       public int StepsFromFirst(int data){
            int k = 0;
            Node Current = first;
            while (Current != null)
            {
                if(Current.data == data) {
                    return k;
                }
                Current = Current.next;
                k++;
            }
            return k;
        }

        //given List is not empty;
        public void RearrangeListToHaveDataFirst(int data){
            Node Current = first;
            while (Current != null){
                if(Current.data == data){
                    break;
                }
                // DeleteFirstNode
                if(first.next == null){
                    last = null;
                }else {
                    first.next.previous = null;
                }
                first = first.next;

                // InsertLast
                Node newNode = new Node();
                newNode.data = Current.data;
                if(IsEmpty())
                {
                    first = newNode;
                }else {
                    last.next = newNode;
                }
                newNode.previous = last;
                this.last = newNode;

                //
                Current = Current.next;
            }
        }

        public void displayForward(){
            System.out.println("List (first --> last) ");
            Node Current = first;
            while (Current != null){
                Current.displayNode();
                Current = Current.next;
            }
            System.out.println();
        }


    }

    public static void main(String[] args) throws Exception {
        CustomLinkedList cll = new CustomLinkedList();

        Scanner sc = new Scanner(System.in);

        // Number of Elements in the list
        int N = sc.nextInt();

        // Number of Elements to be removed
        int M = sc.nextInt();

        // Initialize List with consecutive order
        for(int i =N;i>0;i--){
            cll.InsertFirst(i);
        }

        //cll.displayForward();

        // Count steps 2 and 3
        int counter = 0;

        for(int i=0;i<M;i++){
            // Element to be removed
            int a = sc.nextInt();

            // Number of steps from the First element
            int k = cll.StepsFromFirst(a);

            if((N-i-k) > k){
                counter += k;
            }else{
                counter += (N-i-k);
            }

            cll.RearrangeListToHaveDataFirst(a);
            cll.DeleteFirstNode();
            //cll.displayForward();


        }

        System.out.println(counter);
    }

}

글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.