백준 2346번: 풍선 터뜨리기 with Java

풍선 터뜨리기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

4 MB

32169

13473

10892

43.661%

문제

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 복사

5
3 2 1 -3 -1

예제 출력 1 복사

1 4 5 3 2

 

 

 

---

 

풍선 뭐임 ㅡㅡ? 어휴 인덱스 0에서 시작해서 그 알맹이 따라서 인덱스 바꿔주면.. 되지 않나....

일단 해보도록 하자

아 잠깐 풍선 터뜨리면 그 풍선 사라지는 것 같음 이런 ㅁㅊ 이걸 어케 해요

 

생각을 해봤다.

정상적으로 더했을 때 인덱스 안에 안착했을 때(내가 알 바x)

더했는데 n - 1보다 큰 숫자 나왔을 때

뻈는데 0보다 작은 숫자 나왔을 때

+++++풍선 삭제도..

 

진짜 전혀 모르겠다....................

배열 자체를 바꿔...? 근데 그럼 인덱스가 죽지 않나......

터진 거를 0으로 바꾼 다음에 0인 횟수를 더해보는 건 어때... 참.... 속도가 느릴 것 같지만 아무 생각도 안 드니 이걸로 밀어본다.

 

기각기각 5개 풍선 있을 때 인덱스 3이었을 때 -5가 나오면.... 우짜나요 아ㅡ 뭐 어쩌란 말이냐

일반 배열은 안 될 것 같고 그 예전에 배웠던 링크드리스트였나 이거 쓰면 어찌 될 것 같기도 하고? 그거는 맨 끝이 맨 처음하고 연결되어있지 않았나 하 참 근데 그거 1년 전에 배워서 벌써 가물가물...........

 

링크드리스트 열심히 구글링했다...

int[] 배열 넣어줬고 풍선 번호랑 풍선 안 숫자 넣어줌

index 변수를 따로 사용(0으로 세팅)

remove를 사용해서 삭제하면서 반환되는 int[] 배열을 current에 저장하게 한다. current[0]에 풍선 번호가 저장되어 있기 때문에 결과에 추가, current[1]는 이동할 변수니까 잘 가공해서 index로 넣어주기!! 

 

~양심 고백 타임~

솔직히 너무 힘들어서 구글링 코드 참고 족굼...햇습니다 어쩔 수 없었습니다 너무 어려워!!!!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());	// 풍선 개수 int 변환
		String[] strNums = br.readLine().split(" ");	// 풍선 안에 있는 숫자 값
		LinkedList<int[]> nums = new LinkedList<>();	// 풍선 번호랑 숫자 담을 linkedlist
        for (int i = 0; i < n; i++) {
        	nums.add(new int[] {i + 1, Integer.parseInt(strNums[i])});
        }	// i + 1은 풍선 번호, 풍선 안 숫자는 String으로 입력받았기 때문에 int형으로 바꾸어서 리스트에 추가해줌
		
        StringBuilder result = new StringBuilder();	// 결과 담음
        int index = 0;	// 터뜨릴 풍선 index
        
        // nums 리스트가 비어있지 않을 동안 반복
        while (!nums.isEmpty()) {
            int[] current = nums.remove(index);	// index 풍선 터뜨리고 배열에 인덱스랑 풍선 안 숫자 들어감
            result.append(current[0]).append(" ");	// 터뜨린 풍선 번호 result에 추가
            int move = current[1];	// 풍선 안 숫자

            if (nums.isEmpty()) break;	// 풍선 다 터졌으면 나가자
            
            if (move > 0) {
                index = (index + (move - 1)) % nums.size();
            } // 양수일 경우 오른쪽으로 이동 
            else {
                index = (index + move) % nums.size();	// 음수면 왼쪽으로 이동
                
                if (index < 0) {
                    index += nums.size();
                }	// index가 0보다 작아질 경우 사이즈 더해줌
            }
        }
        System.out.println(result);
	}
}

 

 

넨 맞았어요^&^ 너무 어렵네요 풍선은 전부 한 방에 기관총으로 쏴버립시다!!!!!!!!!!!!!