연결리스트를 배우고 백준에 응용해보았다.
이 문제는 재도전한거였는데 음수를 생각하지 못하고 풀었어서 문제가 살짝 꼬였었다..
#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;
}