[백준] 1966 프린터 큐 - 덱 + 원형 JAVA

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

2346번: 풍선 터뜨리기

코드설명

덱 혹은 배열을 원형으로 생각하여 진행할 수 있습니다.

 

 

덱을 사용할때의 문제로직입니다.

 

덱 사용시 주의해야할점은, Deque를 LinkedList(이중연결리스트)로 사용하면 메모리초과가 납니다. 

ArrayDeque를 사용하는것이 메모리초과를 해결할 수 있습니다.

ArrayList의 데이터조회 시간복잡도는 모든 데이터 접근시 O(1)의 시간복잡도 입니다.

반면 LinkedList의 데이터조회 시간복잡도는 데이터의 위치에 따라 달라집니다.

public static Deque<Node> deque = new ArrayDeque<Node>();

 

Array배열을 사용하여도 풀어보았습니다.

index = (index + move) % size;
if(index < 0) {
    index += size;
}

위와 같은 코드를 통해 index의 위치를 계속해서 갱신해갑니다.

여기서 만약에 index가 size보다 더 큰 음수라면 어떻게해야할까 라는 고민이 생길 수 있습니다.

문제조건에 [종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. ] 라는 조건이 있으므로 어떻게해서든 index의 값은 아무리 이동하더라도 N보다 작기에 상관 없습니다.

 

 

코드

덱을 사용하여 푼 코드

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

public class Main {
	public static int N;
	public static int answer = 0;
	public static Deque<Node> deque = new ArrayDeque<Node>();
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		int num = Integer.parseInt(st.nextToken());
    		deque.offer(new Node(i,num));
    	}
		
    	while(!deque.isEmpty()) {
    		Node temp = deque.pop();
    		if(temp == null) break ;
    		int idx = temp.idx;
    		int num = temp.num;
    		sb.append((idx+1)).append(" ");
    		if(temp.num > 0) {
    			if(deque.isEmpty()) break;
    			for(int i=0;i<temp.num-1;i++) {
    				deque.offerLast(deque.pollFirst());	
    			}
    		}
    		else if(temp.num < 0) {
    			if(deque.isEmpty()) break;
    			for(int i=0;i<Math.abs(temp.num);i++) {
    				deque.offerFirst(deque.pollLast());	
    			}    			
    		}
    	}
    	System.out.println(sb.toString());
    }
    
}

class Node{
	int idx;
	int num;
	public Node(int idx, int num) {
		this.idx = idx;
		this.num = num;
	}
}

 

LinkedList를 활용하여 index의 값을 나누면서 

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

public class Main {
	public static int N;
	public static int answer = 0;
	public static LinkedList<Node> list = new LinkedList<>();
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		int move = Integer.parseInt(st.nextToken());
    		list.add(new Node(i, move));
    	}
    	
    	int index = 0;
    	while(!list.isEmpty()) {
    		Node temp = list.get(index);
    		int idx = temp.idx;
    		int move = temp.move;
    		int size = list.size();
    		
    		sb.append(list.get(index).idx + 1).append(" ");
    		list.remove(index);
    		size -= 1;
    		
    		if(move > 0) {
    			move -= 1;
    		}
    		
    		if(size == 0) {
    			break;
    		}
    		index = (index + move) % size;
    		if(index < 0) {
    			index += size;
    		}
    		
    	}
    	
    	System.out.println(sb.toString());
    }
    
}

class Node{
	int idx;
	int move;
	public Node(int idx, int move) {
		this.idx = idx;
		this.move = move;
	}
}