[백준] 2346. 풍선 터뜨리기

문제

 

풀이 과정

이 문제는 N 길이의 리스트가 주어질 때 처음과 끝이 연결된 구조이다.

즉, 원형 연결 리스트로 구현 해결할 수 있다.

 

문제 접근

원형 연결 리스트 구성

Node 클래스 정의

• num: 풍선 번호
• x: 이동 값
• next: 다음 노드
• prev: 이전 노드
• move(int step): step 만큼 이동하여 도착한 노드 반환
  • step > 0(양수) : 다음 노드를 따라 이동
  • step < 0(음수) : 이전 노드를 따라 이동 
•  remove(): 현재 노드를 원형 리스트에서 제거

static class Node {
    int num;
    int x;
    Node next;
    Node prev;
    
    public Node move(int x) {
        Node cur = this;
        if (x > 0) {
            for (int i = 0; i < x; i++) {
                cur = cur.next;
            }
        } else {
            for (int i = x; i < 0; i++) {
                cur = cur.prev;
            }
        }
        return cur;
    }

    public void remove() {
        this.prev.next = this.next;
        this.next.prev = this.prev;
    } 
}

 

원형 리스트 구성

• N개의 노드를 만들어 연결한다.
• 첫번째 노드와 마지막 노드를 서로 연결해준다.

Node[] nodes = new Node[N];

// N개의 노드를 만들어 연결
for (int i = 0; i < N; i++) {
    Node node = new Node();
    node.num = i + 1;
    node.x = Integer.parseInt(st.nextToken());
    nodes[i] = node;

    if (i == 0) {
        continue;
    }
    nodes[i - 1].next = node;
    nodes[i].prev = nodes[i - 1];
}

// 첫번째 노드와 마지막 노드를 연결 => 원형 구조
nodes[0].prev = nodes[N - 1];
nodes[N - 1].next = nodes[0];

 

시뮬레이션

• 첫번째 풍선부터 시작해서 풍선을 제거하고 이동값만큼 이동하면 된다.
• 이를 풍선 개수 만큼 반복한다. 

 

코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static class Node {
        int num;
        int x;
        Node next;
        Node prev;

        public Node move(int x) {
            Node cur = this;
            if (x > 0) {
                for (int i = 0; i < x; i++) {
                    cur = cur.next;
                }
            } else {
                for (int i = x; i < 0; i++) {
                    cur = cur.prev;
                }
            }
            return cur;
        }

        public void remove() {
            this.prev.next = this.next;
            this.next.prev = this.prev;
        }
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Node[] nodes = new Node[N];
        for (int i = 0; i < N; i++) {
            Node node = new Node();
            node.num = i + 1;
            node.x = Integer.parseInt(st.nextToken());
            nodes[i] = node;

            if (i == 0) {
                continue;
            }
            nodes[i - 1].next = node;
            nodes[i].prev = nodes[i - 1];
        }

        // 원형 연결리스트
        nodes[0].prev = nodes[N - 1];
        nodes[N - 1].next = nodes[0];

        Node cur = nodes[0];
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < N; i++) {
            answer.append(cur.num).append(" ");

            // 현재 노드 삭제
            cur.remove();

            int step = cur.x;

            if (i == N - 1) {
                break;
            }

            cur = cur.move(step);
        }

        bw.write(answer.toString());
        bw.flush();
        bw.close();
    }
}