백준 2346번 문제. 풍선 터뜨리기

백준 2346번 문제. 풍선 터뜨리기

[Point] 원형으로 작동할 수 있게끔 하되, <<이동할 때 이미 터진 풍선은 빼고 생각한다>>는 것에 유의하여 "몇 걸음"을 움직였는지 카운팅해줄 것

처음에 이 문제를 보자마자 떠오른 생각은 환형 더블 링크드 리스트였다 (Circular Double Linked List) 

터뜨린 풍선은 앞으론 고려 안한다는 점에서 원형 큐도 좀 생각하긴 했다..

하지만 C언어에서 구현하려면 코드가 생각보다 길어질 것 같아서 어떻게 할까 고민하다가, 그냥 야매로 배열을 사용하기로 결정.

전체적인 알고리즘의 뼈대는 다음과 같다.

<변수 설명>

Remain : 남아있는 풍선의 갯수 

total : 전체 풍선의 갯수 (이 값은 변하지 않는다)

dir : 방향

move : 몇 걸음 이동해야 하는가 (속도 = 속력+방향인것처럼 arr[i]의 값을 몇걸음(move), 무슨방향으로(dir)로 나누었다) 

Index : 현재 알고리즘이 탐색하고 있는 풍선의 번호

nIndex : 다음에 탐색하게 될 풍선의 번호

 

<흐름> 

0. 일단 입력을 받는다 (준비작업)

1. 풍선의 데이터를 확인하여 어느 방향으로 몇걸음 움직여야하는지 계산한다 (move는 절대값, dir은 방향이다)

2. 해당 풍선을 터뜨려 몇 번 풍선을 터뜨렸는지 출력해주고, 데이터를 0으로 만들어준다 (문제 조건에 0은 들어있지 않다고 했으니 0을 이용하여 터뜨림 유무를 판별할 수 있다)

3. 1번과정에서 얻었던 방향으로 move만큼 이동해주되, 만약 방문한 풍선의 데이터가 0이라면 무시하고 move 변수도 그대로 냅둔채 다음 풍선으로 이동시킨다.

방문했던 풍선이 아니라면(터뜨릴 수 있는 풍선이라면), move 변수를 1 깎아줌으로서 "유효이동"이 일어났음을 표시한다.

만약 배열의 범위를 벗어났다면, 반대편쪽 끝으로 인덱스를 이동시켜주어야 한다.

4. 유효이동이 move 걸음만큼 일어났다면 다음 터뜨릴 풍선에 Index가 위치해있다는 의미이다. 위 과정을 1번부터 다시 반복한다 

5. 만약 풍선을 터뜨렸는데(arr[Index]=0) 그로 인해 남아있는 풍선이 더이상 없는 경우(Remain=0), 두번째 while문은 실행되지 않고 첫번째 while문도 빠져나오게 된다. 

6. 출력해주는 과정은 이미 위 2번 과정에서 일어났기 때문에 arr만 도로 free해주면 된다.

#include <stdio.h>
#include <stdlib.h>
 
int main() {
 
    int Remain, total, i, move, nIndex, dir = 1, Index = 0;
    int* arr;
 
    //준비작업//
    scanf("%d", &Remain);
    total = Remain;
    arr = (int*)malloc(sizeof(int)*Remain);
 
    for (i = 0; i < total; i++) {
        scanf("%d", &arr[i]);
    }
 
    //풍선 터뜨리기 시작//
    while (Remain > 0) {
        move=arr[Index]; 
        dir = 1; 
        if (move < 0) { 
            move = -move;
            dir = -1;
        }
 
        arr[Index] = 0; 
        Remain--; 
        printf("%d ", Index+1); 
 
        while (move > 0 && Remain>0) { //아직 걸음수가 남아있고, 터뜨릴 풍선도 남아있는 한 아래과정을 반복수행
            nIndex = Index + dir;
        
            if (nIndex < 0)  
                nIndex = total - 1;
            if (nIndex >= total) 
                nIndex = 0;
            
            
            if (arr[nIndex]!=0) {  
                Index = nIndex;
                move--; 
            }
            else {
                Index = nIndex;
            }
        }
    }
    free(arr);
 
    return 0;
}