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

문제내용

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

2346번: 풍선 터뜨리기

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

---

문제 접근 방법

문제를 읽어보면 알겠지만 무조건 입력받은 첫번째 순서 부터 풍선을 터뜨려야하기 때문에 큐를 이용했다.

큐를 활용하면서 풍선안에 있는 값에 따라 오른쪽, 왼쪽이동을 구분하여 풀었다.

 

내가푼 기본적인 로직은 다음과 같다.

1. 큐 생성
   값에 따라 풍선을 이동시키며 가장앞에 위치한 풍선을 터뜨리기 위해 큐를 생성한다.
2. 큐에 담을 풍선 객체
   기본적으로 출력값은 풍선안에 있는 value값이 아니라 위치값으로 출력해야한다.
   따라서 큐에 담긴 풍선마다 value값과 위치값을 같이 저장시켜줄수 있는 qLocation클래스를 만들어서 큐에 풍선마다 value와 위치를 저장시킨 객체를 넣어준다.
3. 풍선 터뜨리기
   풍선을 하나 터뜨린다는 의미는 큐에서 객체 하나를 poll한다는 의미와 같다. 따라서 큐의 크기가 0이 될때까지 반복하는 while문을 이용했다.
   while문에서의 흐름은 "풍선 하나 터뜨리기 -> 터뜨린 풍선 위치 하나 출력 -> 터뜨린 풍선에 있는 값확인 -> 값이 양수면 오른쪽, 음수면 왼쪽으로 이동하는 메서드 실행" 이고 이를 반복하게 된다.
   
   
4. 오른쪽 이동(풍선안의 값이 양수 일때)
   오른쪽 이동시 필요한 변수가 있다.
   int move -> 터뜨린 풍선으로부터 얻은 값으로 몇번 이동해야 하는지 알려준다.
   int preSize -> 풍선을 터뜨리기전 풍선들의 개수이다. 풍선하나를 터뜨리고 난후의 개수를 알기 위해 필요하다.
   int afterSize -> 풍선을 하나 터뜨리고 난후의 개수이다. move값 계산을 위해 필요하다.
   int nowV -> 현재 터진 풍선의 value값이다. move값 계산을 위해 필요하다.
   
   위의 4가지 변수로 오른쪽으로 얼마나 이동할지 move 값을 계산한다.
   기본적으로 오른쪽 이동시에 "move = nowV % afterSize" 공식을 따른다. preSize가 아닌 afterSize로 하는 이유는 터진 풍선의 위치는 이동시 건너뛰기 때문이다. 위의 것을 풀어서 말하면...
   만약 풍선이 ( 11 5 5 5 5 ) 5개가 있을때 첫번째 풍선은 나머지 4개의 풍선을 2바퀴돌고 3번더 이동하게 된다. 즉, 네번째 5가 다음 순서의 풍선이된다.
   
   다만 주의 할점은 "nowV % afterSize == 0" 이 나올 경우엔 오른쪽끝에 풍선이 다음에 터뜨릴 풍선이라는 것을 알아야한다. 예를들면 풍선이 (8 5 5 5 5) 5개가 있을때 첫번째 풍선을 터뜨리면 다음에 터뜨릴 풍선은 무조건 마지막 풍선이 된다. 따라서 move=0이 나왔을때와 아닐때로 나눠서 이동시켜 주면된다.
   
5. 왼쪽 이동(풍선안의 값이 음수 일때)
   왼쪽이동시 필요한 변수는 오른쪽 이동할때와 같다.
   왼쪽이동도 마찬가지로 nowV % afterSize 를 따르는데 이때 오른쪽 이동과 차이점은
   "move = preSize - (nowV % afterSize)" 라는 점이다.
   preSize로 빼주는 이유를 말해보자면 (nowV % afterSize)는 왼쪽으로 이동했을때의 위치를 나타낸다. 하지만 우리는 큐를 이용하게 되면 왼쪽으로 이동시킬수 없다. 따라서 왼쪽이동을 오른쪽이동 처럼 이동시켜야 하기 때문에 풍선개수에서 왼쪽으로 이동된것만큼 빼주게 되면 오른쪽이로 이동시킨것과 같은 의미가 된다.
   
   한마디로 간단하게 생각하려면 풍선이 5개있다고 할때 (-1 5 5 5 5)를 (8 5 5 5 5)로 만들어준뒤 이동시킨다고 생각하거나, "왼쪽 1번이동 == 오른쪽 4번이동 // 왼쪽 2번이동 == 오른쪽 3번이동 ... "이런식으로 생각하면 편하다.

위의 과정으로 문제를 풀수있다.

자세한 내용은 풀이를 보자.

 

---

풀이

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

public class Main {
	static Queue<qLocation> q = new LinkedList<qLocation>();//풍선담을 큐
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());//풍선개수
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<N; i++) {//풍선 담기
			q.add(new qLocation(Integer.parseInt(st.nextToken()),i+1));
		}
		
		//풍선 번호대로 터뜨리기
		while(true) {
			int preSize = q.size();//이전 풍선개수 변수
			int afterSize = 0;//이후 풍선개수 변수
			qLocation ql = q.poll();//풍선 하나 터뜨리기
			int nowV = ql.val;//터뜨린 풍선 값
			System.out.print(ql.loc+" ");//방금 터뜨린 풍선들 위치를 출력
			
			if(q.size()==0) break;//큐 비었으면 멈춤
			if(nowV>0) rightMove(preSize, afterSize, nowV);//오른쪽으로 이동
			else if(nowV<0) leftMove(preSize, afterSize, nowV);//왼쪽으로 이동
		}
	}
	
	//오른쪽 이동
	public static void rightMove(int preSize, int afterSize, int nowV) {
		int move = 0;//몇번 움직이는지에 대한 변수
		
		afterSize = preSize-1;//위에서 풍선하나 터뜨리고난 후의 개수
		move = nowV % afterSize;//몇번 움직일지 계산
		
		if(move==0) {//나눠 떨어지면 다음 풍선은 무조건 끝에 풍선을 터뜨리는 경우
			for(int i=0; i<afterSize-1; i++) {//-1을 해주는 이유는 다음 터뜨릴 풍선을 큐의 맨앞에 놓기위해서임
				q.add(q.poll());
			}
		}else {//그게 아니면 move-1만큼 이동
			for(int i=0; i<move-1; i++) {//-1을 해주는 이유는 다음 터뜨릴 풍선을 큐의 맨앞에 놓기위해서임
				q.add(q.poll());//다음 터뜨릴 풍선 앞에 올때까지 빼고 넣기 반복
			}
		}
	}
	
	//왼쪽 이동
	public static void leftMove(int preSize, int afterSize, int nowV) {
		int move = 0;
		
		afterSize = preSize-1;//위서 풍선하나 터뜨리고나 후의 개수
		//왼쪽으로 이동의경우 (전체개수 - 나머지값)으로 계산하는데 이는 왼쪽이동을
		//오른쪽이동처럼 해주기 위해서임.
		//이때 오른쪽이동에서 처럼 move==0일땐 절대 안나오게됨. 이유는 preSize를 빼주기 때문이고
		//만약 나머지값이 0이라면 결국 다음 풍선인 제일 앞에 풍선을 터뜨릴 수 있도록 이동수(move)가 계산됨.
		move = preSize - (Math.abs(nowV) % afterSize);//몇번 움직일지 계산
		
		for(int i=0; i<move-1; i++) {////-1을 해주는 이유는 다음 터뜨릴 풍선을 큐의 맨앞에 놓기위해서임
			q.add(q.poll());//다음 터뜨릴 풍선 앞에 올때까지 빼고 넣기 반복
		}
	}
}

//큐에 담을 풍선의 값과 위치를 나타내줄 클래스
class qLocation{
	int val;
	int loc;
	public qLocation(int val, int loc) {
		this.val = val;
		this.loc = loc;
	}
}

---

마치며

큐만을 이용해 푸는건 솔직히 쉽지 않았다. 그래서 다른 분들 풀이를 찾아보니 list와 데크로 풀었는데 그게 좀더 쉬운 풀이라고 생각이들긴 한다. 그래도 내풀이는 효율이 덜 나올지라도 잘풀은거라고 스스로 위안해본다ㅎㅎ..