백준 자바 2346 알고리즘 풍선 터뜨리기 문제' 문제풀이

풍선 터트리기 백준 2346번 문제는

전에 풀었던 요세푸스 문제와 매우 유사합니다

링크드리스트(Linked List) 문제이며.

배열없이 Linked List를 이용해 풀었습니다.

원형 링크드리스트(Circular Linked List) 문제입니다.

백준 1158번 문제 링크

More info: 요세푸스 문제

코드 설명

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

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





백준 2346번 문제 링크

More info: 풍선 터뜨리기 문제





자바는 여기서 배웠습니다

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





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

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

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

import java.util.Scanner;

public class Main {
    static int ValueBeingRemoved = 1;

    public static class Node {

        int data_row;
        Node next;
        Node previous;

        public void displayNode_data_row(){
            System.out.print(data_row);
        }

    }

    public static class CustomLinkedList {
        Node first;
        Node last;

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

        // 풍선 값을 입력 및 정렬
        public void InsertFirst(int data_row){
            Node newNode = new Node();
            newNode.data_row = data_row;

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

            last.next = newNode;
            newNode.previous = last;
        }

        // 풍선이 비어있는지 확인
        public boolean IsEmpty(){
            return first == null;
        }

        // 풍선 정보 출력
        public void DisplayAll(){
            Node temp = new Node();
            temp = last;
            Node newNode = new Node();
            newNode = first;
            if(IsEmpty()!=true)
            {
                while (temp.data_row != newNode.data_row)
                {
//                    System.out.print(temp.data_row);
//                    System.out.print(" ");
                    temp = temp.previous;
                }
//                System.out.print(temp.data_row);
//                System.out.println();
            }
        }



        public int Balloon(int sn, int d){

         int counter = 0;

         // 처음에는 1을 없앤다
         if (sn == 1)
         {
             counter = d;
         }

         // start from where data = sn
         Node newNode = last;

         if(IsEmpty())
         {
             return 0;
         }

//            System.out.println();
//            System.out.println("first + last");
//            System.out.println(first.data);
//            System.out.println(last.data);
//            System.out.println();

         while (newNode.data_row != sn){
             newNode = newNode.previous;
         }

            //System.out.println("d : "+ d);

         // find data with d distance away
            if(counter > d){
                while (counter > d){
                    newNode = newNode.next;
                    //System.out.println("counter : " + counter + " newNode : " + newNode.data_row);
                    counter--;
                }
            }
            else if(counter < d){
                while (counter < d-1){
                    newNode = newNode.previous;
                    //System.out.println("counter : " + counter + " newNode : " + newNode.data_row);
                    counter++;
                }
            }
//            if(d == 0){
//                System.out.println("0은 적혀있지 않음");
//            }

         // print number being deleted
//            System.out.println();
            ValueBeingRemoved = newNode.data_row;
            System.out.print(ValueBeingRemoved);

//            System.out.println();

         // allocation dData
//            System.out.println();
//            System.out.print("dData : " + newNode.dData);
//            System.out.println();

         // allocate next number
         sn = newNode.previous.data_row;

         // delete corresponding Node
         // when newNode is last
         if(newNode == last){
             newNode.next.previous = newNode.previous;
             newNode.previous.next = newNode.next;
             last = newNode.previous;
         }else {
             newNode.next.previous = newNode.previous;
         }

         // when newNode is first
         if(newNode == first){
             newNode.next.previous = newNode.previous;
             newNode.previous.next = newNode.next;
             first = newNode.next;
         }else {
             newNode.previous.next = newNode.next;
         }
         return sn;

        }
    }

    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();

        // Directional Data
        int [] paperNumbers = new int[N+1];

        // Initialize List with consecutive order
        for (int i = 1; i <= N; i++) {

            // Directional Data
            paperNumbers[i] = sc.nextInt();
            cll.InsertFirst(i);
        }

        // show all elements
        // cll.DisplayAll();

        // Starting number
        int sn = 1;

        //balloon Problem
        for (int i = 0; i<N; i++){
            //System.out.println();
            //cll.DisplayAll();
            //System.out.println();
            //System.out.println("sn :" + sn);
            sn = cll.Balloon(sn, paperNumbers[ValueBeingRemoved]);
            if (i == N-1)break;
            System.out.print(" ");
        }


    }
}

글을 마치며

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

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

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

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

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

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

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

오늘하루도 즐거운 하루 되세요~