TIL

LinkedList 연습을 하기 위해 LinkedList 카테고리의 문제를 풀려했는데
황당하게도 LinkedList를 사용하면 메모리 초과가 나는 문제였다...
뭐 문제 자체도 다른 사람 풀이를 보고 풀었긴 했는데.. 아무튼 웃프다.

백준 2346번: 풍선 터뜨리기

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

몰랐던 풀이 방법들을 알게 된 문제..

1. ArrayDeque의 자료형을 배열 int[]로 정하고
   => ArrayDeque<int[]> q= new ArrayDeque<>();

2. 배열에 풍선 번호와 풍선 속 종이의 수를 저장한 뒤
   => int[] arr= {i+1,Integer.parseInt(st.nextToken())};

3. 그 배열을 ArrayDeque에 넣는 방식..
   => q.add(arr);

4. 그 후 덱의 사이즈가 1이 될 때까지 (종이 속 숫자 -1) 만큼 숫자를 뒤로 보낸다.
   (음수이면 앞으로 보낸다)

언제 덱을 써야하는지 언제 연결리스트를 써야하는지 이런 부분에 대해 감이 안오는 것 같다.
특히 이 문제는 연결리스트로 풀이하면 메모리 초과가 나는데, 각 자료구조 클래스가 메모리 크기나 실행 속도에 미치는 영향도 좀 공부해야겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n= Integer.parseInt(br.readLine());
		ArrayDeque<int[]> q= new ArrayDeque<>();
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		for(int i=0;i<n;i++) {
			int[] arr= {i+1,Integer.parseInt(st.nextToken())};
			q.add(arr);
		}
		
		while(q.size()>1) {
			int[] arr=q.pollFirst();
			bw.write(arr[0]+" ");
			int k=arr[1];
			if(k>0) {
				for(int j=1;j<k;j++) {
					q.addLast(q.pollFirst());
				}
			}else {
				for(int j=k;j!=0;j++) {
					q.addFirst(q.pollLast());
				}
			}
		}
		bw.write(String.valueOf(q.poll()[0]));
		bw.flush();
		bw.close();
	}
}