백준 2346번 문제 - 풍선 터뜨리기(java)

백준 2346번 문제 - 풍선 터뜨리기(java)

728x90

백준 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번째 풍선부터 터뜨리며 그 안에 있는 수(예제에서 3)만큼을 이동해서 다시 풍선을 터뜨리는 개념입니다.

처음에는 3 2 1 -3 -1 순으로 풍선이 존재했다면, 1번째 풍선을 터뜨리고 난 후에는 2 1 -3 -1 순으로 존재하고 이때 첫 번째 풍선의 3번째 뒤의 풍선인 -3까지 도달하게 됩니다. 그리고 다시 -3칸을 이동하는데 -3이 존재하던 칸을 기준으로 1 -> 2 -> -1 순으로 돌아서 5번째 풍선이 터진 것을 알 수 있죠. 이를 통해 터뜨릴 때는 그 풍선이 존재한다고 생각하고 움직이고, 이미 터뜨린 풍선은 없는 풍선으로 가정해서 움직인다는 것을 파악할 수 있습니다.

그래서 저는 크기가 고정되어 있는 배열보다는 ArrayList를 이용해서 코드를 작성했습니다.

import java.io.*; import java.util.ArrayList; import java.util.StringTokenizer; class Node { int position; int move; Node(int position, int move) { this.position = position; this.move = move; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int balloonCount = Integer.parseInt(br.readLine()); ArrayList balloon = new ArrayList<>(); StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0;st.hasMoreTokens();i++) { balloon.add(new Node(i+1,Integer.parseInt(st.nextToken()))); } int move = 0; int location = 0;//현재 위치 StringBuilder sb = new StringBuilder(); while (true) { int pos = position(balloon.size(), location + move); //위치 파악 move = balloon.get(pos).move; location = move>0? pos-1 : pos; //앞으로 움직이는 경우 사라지는 현재 위치의 풍선도 고려 sb.append(balloon.get(pos).position).append(" "); balloon.remove(pos); if(balloon.size() == 0) break; } System.out.println(sb.substring(0, sb.length()-1)); //마지막이 공백이기 때문에 제거해줘야 함 } public static int position(int max, int location) { if(location<0) return position(max, location + max); //위치가 리스트보다 작은 경우 else if(location>= max) return position(max, location - max); //위치가 리스트를 넘긴 경우 else return location; //리스트 내에 위치가 존재하는 경우 } }

따로 코드 설명을 적기 애매한 내용이네요. 일단 현재 위치를 파악하고, 풍선에 적혀 있는 숫자(move)만큼 움직이는데 충실하고자 하는 코드를 작성했습니다. 이를 잘 신경쓴다면 코드는 쉽게 작성하실 수 있을 겁니다!

코드를 작성하는데 있어 생각의 편의를 위해 Node라는 클래스를 만들어 처리했습니다. 꽤 복잡해 보이는 코드임에도 불구하고 이 코드가 java11의 상위권에 있다는 것이 의문이긴 하네요.(그걸 모르는게 제 실력 부족을 나타내는 것이라 봅니다.)

728x90

from http://no-dev-nk.tistory.com/53 by ccl(A) rewrite - 2021-10-15 11:01:59