[백준][Java] 2346번 풍선 터뜨리기 (덱, linkedlist)

index를 맞춰줘야되는 문제라 좀 짜증났음

paper가 음수로 쓰인 경우만 신경써서 처리해주면

paper가 양인 경우는 손쉽게 풀 수 있음

 

덱으로 하는 경우에는 진짜 풍선 넘어가면서 시뮬레이션하면서 푸는 코드가 더러 있었는데

제한조건이 N(1 ≤ N ≤ 1,000)로 작아서 그렇지 (그냥 자료구조 써보라고 낸 문제니까)

N진짜 커지면 그냥 터지는 코드임 무조건 index만 조절해줘서 풀어야함

simulating해주면 시간낭비 메모리낭비임

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] paperArr = new int[N];
        String[] str = br.readLine().split(" ");
        for(int i=0; i<N; i++)
            paperArr[i] = stoi(str[i]);
        
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=1; i<=N; i++)
            list.add(i);
        
        int currIdx = 0;
        while(true) {
            int currValue = list.remove(currIdx);
            sb.append(currValue+" ");
            if(list.isEmpty()) break;
            
            int paper = paperArr[--currValue];
            //paper가 음수일 때만 잘 처리해주면 됨..
            if(paper>0) {
                --currIdx;
                currIdx=(currIdx+paper)%list.size();
                
            }
            else {
                paper=Math.abs(paper);
                paper=list.size()-(paper%list.size());
                currIdx=(currIdx+paper)%list.size();
            }
        }
        System.out.println(sb.toString());
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}