BOJ - 풍선 터뜨리기

leehyunjon·2022년 10월 27일

ArrayDeque Deque boj 자료구조

Algorithm

목록 보기

117/162

풍선 터뜨리기 2346 : https://www.acmicpc.net/problem/2346

Problem

Solve

첫번째 풀이

처음에는 배열을 이용해서 현재 index에서 move만큼 움직이되 boolean[]을 이용해서 move만큼 한칸씩 이동하되 해당 풍선이 터져있는 곳이라면 움직임 카운트를 하지 않고 이동하는 식으로 구현했습니다.

통과는 되었지만, 좀 더 맛있게(?) 푸는 방법이 있을것 같다 다른 분들의 풀이를 참고하여 Deque으로 구현하는 방법이 있다는 힌트를 보고 다시 구현하였습니다.

두번째 풀이

Deque에 index와 풍선에 들어있는 move값을 배열로 저장하고 터트린 풍선의 move를 기준으로 Deque에 있는 요소를 앞,뒤로 빼고 넣는 식으로 구현할 수 있었습니다. (Deque를 사용한 이유)

move가 양수인 경우
현재 요소의 오른쪽으로 이동해야하기 때문에, Deque의 앞 요소를 빼서 뒤에 저장하는 식으로 move-1만큼 반복합니다.
그렇게 되면 다음 move에서 Deque의 맨 앞 요소가 우리가 터트릴 풍선이 나오게 됩니다.
move가 음수인 경우
현재 요소의 왼쪽으로 이동해야하기 때문에, Deque의 뒷 요소를 빼서 앞으로 저장하는 식으로 move-1만큼 반복합니다.
그렇게 되면 다음 move에서 Deque의 맨 마지막 요소가 우리가 터트릴 풍선이 나오게 됩니다.

이를 Deque가 빌때까지 반복하게 되면 모든 요소를 처리할 수 있게 됩니다.

주의사항

두번째 Deque를 이용해 구현하는 과정에서 자꾸 메모리 초과가 발생하였습니다.
왜맞틀을 하는 도중에 자료구조에서 몰랐던 부분을 하나 알게되었습니다.

저는 항상 Deque의 구현클래스를 LinkedList로 해왔었습니다. 근데 찾아보니 LinkedList말고 ArrayDeque라는 구현클래스도 있더군요.

stackoverflow에서 찾아보니 이유를 알 수 있었습니다.

LinkedList
LinkedList는 내부 요소가 순차적으로 저장은 되어있지만, 메모리 주소에 연속적으로 저장되어 있지 않기 때문에 캐시 친화적인 자료구조가 아닙니다. 또한 ArrayDeque에 비해 메모리 사용량이 많이 사용된다고 합니다.
그래서 반복 계산에서 자기 자신을 삭제하는 경우에 효율적이라고 합니다.
ArrayDeque
ArrayDeque는 Deque에서 앞,뒤의 요소를 삽입,삭제하는 경우 효율적이라고 합니다.

그래서 LinkedList가 아닌 ArrayDeque를 사용하니 메모리 초과 문제를 해결할 수 있었습니다.

참고로 Queue나 Deque같은 경우 중간에 값이 삽입되거나 삭제되는 경우가 없기 때문에 중간 삽입,삭제가 효율적인 LinkedList보다 ArrayDeque를 이용해서 캐시 친화적이고 효율적인 메모리 사용이 가능해집니다.

Code

2번째 풀이

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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Deque<int[]> dq = new ArrayDeque<>();
		for(int i=1;i<=N;i++){
			dq.offer(new int[]{i, Integer.parseInt(st.nextToken())});
		}

		StringBuilder sb = new StringBuilder();
		int[] info = dq.poll();
		sb.append(info[0]).append(" ");
		int move = info[1];

		while (!dq.isEmpty()){
			if(move>0){
				for(int i=1;i<move;i++){
					dq.offerLast((dq.pollFirst()));
				}
				info = dq.poll();
				sb.append(info[0]).append(" ");
				move = info[1];
			}else{
				for(int i=1;i<Math.abs(move);i++){
					dq.offerFirst(dq.pollLast());
				}
				info = dq.pollLast();
				sb.append(info[0]).append(" ");
				move = info[1];
			}
		}

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

1번째 풀이

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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] ballons = new int[N];
		for(int i=0;i<N;i++){
			ballons[i] = Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();
		boolean[] check = new boolean[N];
		int index = 0;
		int count = 0;

		while(count<N){
			check[index] = true;
			count++;
			sb.append(index+1).append(" ");

			if(count==N) break;

			int move = ballons[index];
			int nextIndex = index;
			int nextCount = 0;
			while(nextCount < Math.abs(move)){
				if(move > 0){
					nextIndex = (nextIndex+1)%N;
				}else{
					nextIndex--;
					if(nextIndex < 0) nextIndex = N+nextIndex;
				}
				if(!check[nextIndex]) nextCount++;
			}
			index = nextIndex;
		}

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