백준 2346번 풍선 터뜨리기

연결리스트를 배우고 백준에 응용해보았다.

이 문제는 재도전한거였는데 음수를 생각하지 못하고 풀었어서 문제가 살짝 꼬였었다..

#include <stdio.h>
#include <stdlib.h> // 이게 없어서 실행이 안돼서 고생했다 ㅎㅎ...

struct list {
	int data; // 풍선에 적힌 숫자
	int index;//풍선의 순서
	struct list* pre; // 이전 풍선의 주소
	struct list* next; // 다음 풍선의 주소
};

struct list* moveright(struct list* cur, int n) //cur와 풍선에 적힌 숫자
{
	int i;
	for (i = 0; i < (n - 1); i++)
	{
		cur = cur->next; // 3 1 2 -1 -2 에서 처음 cur이 5번쨰 칸이라 하자. 여기서 deleteprint하면 3이 사라지고 거기서 moveright(3)을 하면 2칸을 움직이므로 cur는 2 즉, -1이 사라진다.  
	}
	return cur; // cur의 주소를 줘야 delete가능
}

struct list* moveleft(struct list* cur, int n) // cur와 풍선에 적힌 숫자
{
	int i;
	n = (-1) * n;
	for (i = 0; i < n; i++)
	{
		cur = cur->pre; // 3 1 2 -1 -2에서 cur을 -1이라 하자. -2가 삭제되면 cur은 1이 되고 2를 삭제.
	}
	return cur;
}

int deleteprint(struct list* cur) // 가장 문제가 있을 확률이 높은 함수, cur를 받아오면 cur바로 다음 칸을 삭제.
{
	int number;
	struct list* temp;
	temp = (cur->next)->next;  // 3 1 2가 있다 가정 그럼 cur이 3 이면 temp는 2
	number = (cur->next)->data; // number는 1
	printf("%d ",(cur->next)->index); // 풍선의 index를 출력
	free(cur->next); // 1을 free하자.
	cur->next = temp; //3의 next는 이제 2
	(cur->next)->pre = cur; // 2의 pre는 이제 3
	return number; //그리고 1을 return
}

int main()
{
	int i, N, x;
	int number;
	struct list* ptr1;
	struct list* ptr2;
	struct list* temp;
	struct list* cur;
	scanf("%d", &N);
	ptr1 = (struct list*)malloc(sizeof(struct list));
	temp = ptr1; // 첫 칸 주소를 기억해두고 나중에 마지막 칸과 연결해주어야 한다.
	scanf("%d", &x);
	ptr1->data = x; // 첫 칸 데이터 저장
	ptr1->index = 1;
	for (i = 0; i < (N - 1); i++)
	{
		ptr2 = (struct list*)malloc(sizeof(struct list));
		ptr2->pre = ptr1; // i= 0일 떄를 생각해보자. ptr2는 두번쨰 칸이 되고 ptr2의 pre는 ptr1이 된다.
		ptr1->next = ptr2; // ptr1의 다음칸이 ptr2가 된다.
		ptr1 = ptr2; // 이제 ptr2와 세번쨰 칸을 연결해야하므로
		scanf("%d", &x);
		ptr1->data = x; // 두번째 칸의 데이터를 저장
		ptr1->index = (i + 2);
	}
	cur = ptr1; // 반복문이 끝나면 ptr1은 마지막 칸이 된다.
	ptr1->next = temp; // ptr1의 마지막 칸의 다음 칸은 첫쨰칸
	temp->pre = ptr1; // 첫쨰칸의 pre는 마지막 칸, 이렇게 모든 리스트가 pre, next로 연결된다.
	for (i = 0; i < (N - 1); i++)
	{
		number = deleteprint(cur); // cur다음칸을 삭제하고 삭제한 칸의 data를 리턴하면서 인덱스 출력
		if (number < 0)
		{
			cur = moveleft(cur, number); //적혀있던 숫자가 음수이면 moveleft
		}
		else
		{
			cur = moveright(cur, number); // 양수이면 moveright (0은 없다)
		}
	}
	printf("%d", cur->index); //이 과정을 N-1회 하므로 마지막에 한칸 남으므로 마지막 한칸의 index를 출력
	return 0;
}

배열을 사용한 코드를 한번 읽어보자.
f52985님의 코드다.

#include <stdio.h>

int move[1000];

int main()
{
	int i,n;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",move+i);
    //move라는 배열에 풍선에 적힌 수를 모두 저장
	int d=1,l=0,cur=0; //d와 l과 cur를 초기화
    이후 l은 이전 move[cur] 즉, 터뜨린 풍선에 적힌 숫자를 저장한다.
    for(i=n;i;i--) //n번 동안 중괄호안의 연산을 시행, 아마 풍선을 제거하는 연산이다.
	{
		d=l>0?1:-1;//l이 0초과면 d는 1 아니면 d는 -1 
		l=l>0?l:-l;//l이 0초과면 l은 l 아니면 l은 -l
		while(l) (l이 0이 아닌 동안)
		{
			cur=d>0?(cur+1)%n:(cur+n-1)%n;//cur는 d가 양수이면 즉, l이 양수이면 cur은 (cur + 1)을 n으로 나눈 나머지
            d가 0이하의 정수이면 즉, l이 음수이면 (cur +n - 1)을 n으로 나눈 나머지이다. (이는 음수의 나머지가 아닌 양수의 나머지를 계산하기 위하여)
            아! 이는 cur에서 한칸씩 이동하는 연산이다.
			if(move[cur]) l=(l-1)%i;//배열에 저장된 수가 0이 아니면, 즉 터진적 없는 풍선이면 l은 l-1 을 i로 나눈 나머지
            i는 n부터 시작하여 0이 될 때까지 1씩 작아진다.
		}
        //예시를 들어보자. 2 1 -2 를 예시로 들어보자.
        처음에 cur = 0, d = 1 l = 0
        l은 0 초과가 아니므로 d는 1
        마찬가지로 l은 0 초과가 아니므로 l 은 -l 즉 0
        while(l)인데 l은 0이므로 반복문을 빠져나와서 1을 print하고
        l = 2, move[0] = 0
        
        
        그 다음으로 l = 2, move배열은 0 1 -2
        d는 l이 0 초과이므로 1
        l은 l이 0 초과이므로 2
        while(l)
        cur는 (cur + 1)/3 즉 1
        move[1]은 0이 아니므로 l은 2-1 / 2 (현재 i는 3에서 -1해서 2) 이를 하는 이유는 i는 현재 풍선의 개수! 쓸데없는 연산을 줄이기 위하여 나머지를 이용하는 것.
        따라서 l은 1
        
		printf("%d ",cur+1);//연산을 한번 시행하고 나면 cur+1을 출력, 즉, cur가 삭제된 칸이 몇번째 배열인지 뜻하는 것.
        cur + 1을 하는 이유는 배열은 0번째부터 시작하기 때문이고.
		l=move[cur];//l은 시행이 끝나고 move[cur]를 받아온다.
		move[cur]=0;//그러고 move[cur]는 0으로 대체
	}
	return 0;
}

내가 이해하고 다시 짜본 코드

#include <stdio.h>

int main()
{
	int i, count, N, cur = 0; //count는 풍선의 개수, N은 처음 주어진 풍선의 개수, cur는 현재 터뜨릴 풍선 후보의 위치
	int balloon[1000];//각 풍선에 쓰여진 숫자를 저장하는 배열
	int sign, number = 0;//sign은 부호, number는 풍선에 쓰여진 숫자, 처음에는 첫 픙선을 바로 터뜨리기 위해 number를 0으로 초기화
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &balloon[i]);
	}
	for (count=N; count; count--) //풍선의 개수를 하나씩 줄이며 0이 되면 실행중지
	{
		sign = number >= 0 ? 1 : -1;
		number = number >= 0 ? number : (-1) * number;
		while (number)
		{
			cur = sign > 0 ? (cur + 1) % N : (cur - 1 + N) % N; // number의 부호가 -이면 왼쪽으로 한칸, +이면 오른쪽으로 한칸
			if (balloon[cur]) //balloon[cur]가 0이 아니면
			{
				number = (number - 1) % count; //어차피 count개수만큼 몇바퀴 돌고 제자리로 돌아올테니 나머지 연산
				// 이 떄 number는 양수로 만들어주었으니 횟수이다. 0인 즉, 이미 터진 풍선을 만나면 줄어들지 않고 안 터진 풍선을 만나면 하나씩 줄어든다.
			}
		}
		printf("%d ", cur + 1);
		number = balloon[cur];
		balloon[cur] = 0;//터지면 0으로!
	}
	return 0;
}