[백준 2346] 풍선 터뜨리기 - JAVA

https://www.acmicpc.net/problem/2346

 

덱 문제

 

리스트 기반으로 점화식을 세워서 풀었다.

덱보다 성능은 좋을 것 같고, 대신 문제 난이도는 어려워졌다.

 

 

다음 풍선 위치 구하기

 

풍선에 쓰인 수가 양수 :

1. 다음 인덱스 = (현재 인덱스 + 쓰인 수 - 1) % 현재 리스트 사이즈

(-1 하는 이유 : 리스트에서 idx번째 원소를 remove했으므로, idx가 기존의 idx+1번째 원소를 가리키는 것 상쇄)

 

풍선에 쓰인 수가  음수 :

1. 다음 인덱스 = (현재 인덱스 + 쓰인 수)  % 현재 리스트 사이즈

(왼쪽으로 탐색하니 -1 하지 않는다.)

 

2. 1번 값이 음수라면, 다음 인덱스 = 현재 리스트 사이즈 + 다음 인덱스

(파이썬처럼 -1, -2가 size - 1, size - 2번째 원소를 가리키는 취급한다. 이를 실제 인덱스로 변환하는 과정)

 

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

public class Main {

  static class B {

    int i, n;

    B(int i, int n) {
      this.i = i;
      this.n = n;
    }
  }

  public static void main(String[] args) throws IOException {

    List<B> l = new ArrayList<>();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());

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

    int cur = 0;
    int size = N;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
      B remove = l.remove(cur);
      sb.append(remove.i).append(" ");
      size--;

      if (size == 0) {
        break;
      }

      if (remove.n >= 0) {
        cur = (cur + remove.n - 1) % size;
      } else {
        cur = (cur + remove.n) % size;
        if (cur < 0) {
          cur = size + cur;
        }
      }
    }

    System.out.println(sb);
  }
}