[백준] 2436번: 풍선 터뜨리기 - JAVA

🔗 문제

BOJ 2346 : 풍선 터뜨리기

난이도 - 실버 3
알고리즘 분류 - 자료구조, 덱

💬 풀이

풍선의 정렬 : 1-2-3-4-5-...-N-1-2-3-... (순차적)

가장 첫 번째 풍선부터 시작해 각 풍선에 적힌 정수만큼 이동하여 풍선을 터뜨려나가는 문제이다. 이동할 때는 양수) 오른쪽으로, 음수) 왼쪽으로 의 규칙을 지켜야 하고, 이미 터진 풍선이라면 정렬에서 제외한다.

연결 리스트의 개념에서 노드 전체를 순환하는 방식으로 풍선 간의 이동을 구현하고, 제외되는 풍선은 노드의 링크를 그 다음과 연결하는 방식으로 구현한다.

처음에는 각 위치에 번호를 매기고 풍선 번호에 대한 배열, 삭제되는 순서를 저장하는 결과 배열 등 여러 개의 배열을 만들어 접근하려고 했지만, 너무 메모리를 많이 잡아먹어 비효율적인 코드였다.

이를 LinkedList의 Node 개념으로 접근하여, 노드 객체에 각 데이터와 순서를 저장하고, remove함수를 따로 정의하여 노드(풍선)가 삭제되는 즉시 그 순서를 리턴하는 방식으로 해결할 수 있었다.

즉, 최종적으로 터진 풍선의 번호를 순서대로 출력해야 하므로 번호는 처음에 정의한 노드 객체에 저장하여 삭제하는 즉시 값을 출력하고 Main으로 리턴해준다.

💻 코드

#1 - Node 객체를 생성하여 직접 메소드 정의

package march_3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SingleLinkedList_algo {
    public static class Node<Integer> {
        int data;
        int num_order;
        Node<Integer> next;
        Node<Integer> prev;

        //생성자
        Node(int data, int num_order) {
            this.data = data;
            this.num_order = num_order;
            this.next = null;  
            this.prev = null;
        }

        // 입력받은 수를 헤더 노드부터 시작해 노드로 연결하기 위한 add() 메소드
        public void add(int data, int order) {
            Node<Integer> balloon = this;
            while(balloon.next != null)
                balloon = balloon.next;
            balloon.next = new Node<>(data, order);
            if(balloon.prev == null)
                balloon.prev = balloon.next;  //맨 끝과 맨 처음을 이어주는 원형연결리스트의 형태
		            balloon.next.prev = balloon;  // 노드 순회
        }

        // 풍선을 터뜨리고 리스트에서 연결을 끊어버리는 remove() 메소드
        public int remove(Node<Integer> balloon) {
            //LinkedList에 단 2개의 원소만 남은 경우(자기자신의 이전의 이전은 자기자신으로 다시 되돌아온다)
            if(balloon.prev.prev == balloon) {
                System.out.print(balloon.num_order + " ");
                System.out.print(balloon.prev.num_order + " ");
                return 0;
            }

            //노드 삭제를 위해 링크 연결을 끊고 다시 이어주기
            Node<Integer> temp = balloon.prev;
            temp.next = balloon.next;
            temp = temp.next;
            temp.prev = balloon.prev;
            System.out.print(balloon.num_order + " ");

            return balloon.data;
        }
    }
    

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

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

        Node<Integer> head = new Node<>(Integer.parseInt(st.nextToken()), 1);  //헤더 노드

        for(int i=1; i<N; i++) {
            head.add(Integer.parseInt(st.nextToken()), i+1);
        }

        Node<Integer> flag = head;
        while(flag.next != null)
            flag = flag.next;
        //맨 끝의 노드와 맨 앞의 노드를 서로 연결 (서로의 링크를 가리키도록!)
        flag.next = head;
        head.prev = flag;
        flag = flag.next;

        if(N==1) {
            System.out.println(1);
            return;
        }

        for(int i=1; i<N; i++) {
            int move = flag.remove(flag);
//            System.out.println(move);
            // 이동할 정수가 양수일 때
            if(move > 0) {
                while(move-- > 0)  //오른쪽으로 이동(move가 0이 될 때까지 감소)
                    flag = flag.next; 
            } else {  // 이동할 정수가 음수일 때
                while(move++ < 0)  //왼쪽으로 이동(move가 0이 될 때까지 증가)
                    flag = flag.prev;
            }
        }
    }
}

• add(int data, int order) 입력받은 수를 헤더 노드부터 시작해 순서대로 노드로 연결하기 위한 메소드 가장 끝의 노드가 null일 때 새로운 노드를 추가한다.
  
• remove(Node) 풍선을 터뜨리고 리스트에서 노드를 삭제하기 위해 이전, 이후 노드의 링크를 변경한다.
  

*리스트 인터페이스를 상속받아서 구현한다면 @Override로 필요한 함수에 대해 재정의하여 사용할 수도 있다. ex. 옛날에 했던 것 중 Comparator을 임의의 기준으로 재정의하여 원하는 대로 정렬가능했던 것처럼!

#2 - Java에서 기본 제공되는 LinkedList 사용

package march_3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class SingleLinkedList_algo2 {

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

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] balloon = new int[N];
        ArrayList<Integer> result = new ArrayList<>();
        for(int i=0; i<N; i++) {
            balloon[i] = Integer.parseInt(st.nextToken());
        }

        LinkedList<Integer> list = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            list.add(i);
        }

        int index = 0;
        while(true) {
            int num = list.remove(index);
            result.add(num);

            if(list.isEmpty()) break;

            int move = balloon[num-1];
            if(move > 0) {  // 뽑은 수가 양수인 경우 -> 오른쪽 이동
                --index;
                index = (index+move) % list.size();  //노드 순회의 개념을 나머지 연산으로 접근
            } else {   // 뽑은 수가 음수인 경우 -> 왼쪽 이동 (절댓값으로 처리)
                move = Math.abs(move);
                move = list.size() - (move % list.size());
                index = (index + move) % list.size();
            }
        }
        for(int num : result) {
            System.out.print(num + " ");
        }
    }
}

여기서 연결리스트의 역할은 각 풍선의 고유번호를 저장하고 순서대로 번호를 꺼내와 결과 배열에 저장하는 것이다.

📊 정리

📍 어려웠거나 해결하지 못한 부분

Java에서 기본 제공되는 LinkedList만으로 맨 뒤에서 맨 처음으로, 역순으로 순회하는 방식을 구현하는 것이 어려웠지만, 이를 노드 객체 하나하나로 생각했을 때 훨씬 간단하게 접근할 수 있었다.

📍 오늘의 메모

여러 종류의 배열을 동시에 사용할 때는 정확히 그 배열이 어떤 역할을 하는지를 정의하고 그 특성이 드러나도록 이름을 지정하는 것이 복잡한 알고리즘을 해결할 때 좋은 태도인 것 같다!

자바에서 기본 제공하는 메서드를 어떻게 조합하고 사용할지 감이 안 잡힌다면 직접 일일이 구현하는 것도 나쁘지 않은 방법이라고 생각한다. 그런 의미에서 List 인터페이스를 모두 구현해보는 걸 추천한다. (도움이 많이 됨 👍)