42Seoul - push_swap
문제개요
스택구조인 a와 b가 주어진다. 겹치지 않은 n개의 숫자가 랜덤으로 a스택에 존재한다.
스택b를 활용해 특정한 명령어만으로 스택a에서 n개의 순자를 오름차순으로 정렬하게 해야한다.
명령어
swap a (sa) : a의 가장 위에 있는 두 요소를 교환.
swap b (sb) : b의 가장 위에 있는 두 요소를 교환.
ss: ss sa와 sb를 동시에 실행.
push to a (pa) : b의 가장 위에 있는 요소를 a의 가장 위에 삽입 .
push to b (pb) : a의 가장 위에 있는 요소를 b의 가장 위에 삽입.
rotate a (ra) : a의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막이 된다.
rotate b : (rb) b의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막이 된다.
rr: ra와 rb를 동시에 수행한다.
reverse rotate a (rra) : a의 모든 요소를 1만큼 아래로 이동시킨다. 마지막이 첫 번째가 된다.
reverse rotate b(rrb) : b의 모든 요소를 1만큼 아래로 이동시킨다. 마지막이 첫 번째가된다.
rrr: rra와 rrb를 동시에 수행한다.
구현하기(전처리)
1. 정수가 아닐 때 Error 출력
2. 정수가 중복해서 들어오면 Error 출력
3. Int 범위를 넘어선다면 Error 출력
위의 1, 2, 3의 문제는 기존의 atoi를 활용해서 처리할 수 있다.
int check_numbers(const char *str)
{
int i;
int sign;
int digit_checker;
long long value;
sign = 1;
i = 0;
digit_checker = 0;
value = 0;
while (ft_isspace(*str))
str++;
if (str[i] == '-')
sign = -1;
if (str[i] == '-' || str[i] == '+')
i++;
while (str[i] && str[i] >= '0' && str[i] <= '9')
{
value = value * 10 + (str[i] - '0');
i++;
digit_checker++;
}
if (value * sign > 2147483647 || value * sign < -2147483648
|| digit_checker == 0)
occur_error(1);
return (value * sign);
}
4. 인자가 없거나 인자가 하나밖에 없거나 혹은 이미 정렬됐다면 그냥 종료
들어온 값의 유효성을 확인한 후 중복되는 인자가 있는지도 확인한다.
void check_duplicate(t_stack_data *stack)
{
int i;
int j;
int tmp;
i = 0;
j = 0;
while (i < stack->length)
{
j = i + 1;
tmp = stack->arr[i];
while (j < stack->length)
{
if (stack->arr[j] == tmp)
{
occur_error(1);
}
j++;
}
i++;
}
}5. 인덱싱화
모래시계 알고리즘은 들어온 인풋값이 필요없기에 더 빠른 연산을 위해 인풋값을 인덱싱화 해준다.
예를 들어 1, 4, 5, 2, 9, 6 가 들어온다면 숫자의 크기대로 0부터 인덱싱화 해준다.
1, 4, 5, 2, 9, 6 => [0, 2, 3, 1, 5, 4]
구현하기(알고리즘)
1-1 A스택 (왼) B스택 (오) (인자가 5개 이상일 때)
아래의 그림과 같이 인덱싱된 값 [0, 2, 3, 1] 에 따라 a스택에 정렬된다.
1-2 A스택에서 스택의 최상단 값이 중간 인덱스값보다 크다면 ra로 뒤집기
스택 최상단의 값 top이 인덱스의 중앙값보다 클때만 ra로 뒤집기 때문에 pb로 top인 0을 보내준다.
1-3 A스택 먼저 정렬하기
a스택의 크기가 3이 됐으니 a스택을 한 번 정렬해준다.
1-4 A스택으로 pa하기
이미 정렬된 a스택에 sa로 0을 넣어주면 오름차순으로 정리된 a스택을 가질 수 있다.
2-1.A스택 (왼) B스택 (오) (인자가 5개 이상일 때)
1. 스택a 에서 스택b로 넘기기
알고리즘 적용 i라는 변수를 0이라고 생각하고 i는 0부터 배열의 크기만큼 증가한다, chunk라는 상수를 지정해준다.
a스택의 맨 위의 값인 top을 세 가지로 분기해서 처리한다.
1-1 top이 i보다 작을 때 넘긴다.
1-2 i보다는 크고 I + chunk라는 값보다 작다면 b로 넘기고 한 번 뒤집어 준다.
1-3 I + chunk 보다 크다면 ra로 한 번 뒤집어준다.
void a_to_b(t_stack_data *a, t_stack_data *b, int chunk, int i)
{
int length;
length = a->length - 1;
while (a->length != 0)
{
if (get_top(a) <= i)
{
pb(a, b);
i++;
}
else if (get_top(a) > i && get_top(a) <= i + chunk)
{
pb(a, b);
rb(b);
i++;
}
else if (get_top(a) > (i + chunk))
{
if (i < a->length / 2 && i >= 0)
rra(a);
else
ra(a);
}
length--;
}
}2-2.모래시계 모양으로 b스택으로 정렬되는 a스택의 난수들
2 스택b에서 스택a로 넘기기스택 b의 큰값부터 a로 차례대로 넘기면 오름차순으로 정렬된 스택a를 볼 수 있다
2-1 b를 정렬해나가면서 b에서 큰수부터 a로 넘겨준다.
void b_to_a(t_stack_data *a, t_stack_data *b)
{
int length;
length = b->length - 1;
while (b->length != 0)
{
sort_b(b, length);
pa(a, b);
length--;
}
}2-3. b스택에서 다시 a스택으로 넘기기
-모래시계 알고리즘의 약점
499 497 495 493 491 489 487 485 483 481 479 477 475 473 471 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 469 467 465 463 461 459 457 455 453 451 449 447 445 443 441 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 439 437 435 433 431 429 427 425 423 421 419 417 415 413 411 410 412 414 416 418 420 422 424 426 428 430 432 434 436 438 409 407 405 403 401 399 397 395 393 391 389 387 385 383 381 380 382 384 386 388 390 392 394 396 398 400 402 404 406 408 379 377 375 373 371 369 367 365 363 361 359 357 355 353 351 350 352 354 356 358 360 362 364 366 368 370 372 374 376 378 349 347 345 343 341 339 337 335 333 331 329 327 325 323 321 320 322 324 326 328 330 332 334 336 338 340 342 344 346 348 319 317 315 313 311 309 307 305 303 301 299 297 295 293 291 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 289 287 285 283 281 279 277 275 273 271 269 267 265 263 261 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 259 257 255 253 251 249 247 245 243 241 239 237 235 233 231 230 232 234 236 238 240 242 244 246 248 250 252 254 256 258 229 227 225 223 221 219 217 215 213 211 209 207 205 203 201 200 202 204 206 208 210 212 214 216 218 220 222 224 226 228 199 197 195 193 191 189 187 185 183 181 179 177 175 173 171 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 169 167 165 163 161 159 157 155 153 151 149 147 145 143 141 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 139 137 135 133 131 129 127 125 123 121 119 117 115 113 111 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 109 107 105 103 101 99 97 95 93 91 89 87 85 83 81 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 79 77 75 73 71 69 67 65 63 61 59 57 55 53 51 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 19 17 15 13 11 9 7 5 3 1 0 2 4 6 8 10 12 14 16 18
위와 같은 인풋이 들어온다면 스택의 제일 위 값이 i+chunk보다 크기 때문에 수많은 ra를 해야햔다.
스택a에서 chunk의 구간까지 ra를 하기 때문에 비효율적이다.
if (get_top(a) <= i)
{
pb(a, b);
i++;
}
else if (get_top(a) > i && get_top(a) <= i + chunk)
{
pb(a, b);
rb(b);
i++;
}
else if (get_top(a) > (i + chunk))
{
ra(a);
}
그래서 stack의 top이 i+chunk보다 큰 경우일 때 i가 a스택 크기의 절반보다 작다면 rra로 반대로 뒤집어 버리면 불필요한 연산을 줄일 수 있다.
else if (get_top(a) > (i + chunk))
{
if (i < a->length / 2 && i >= 0)
rra(a);
else
ra(a);
}
모래시계의 시간복잡도
- 최선
ra가 없는 경우가 최고의 시간복잡도가 된다. 그러나 과제에서는 정렬된 경우를 허용하지 않는다.
최선의 시간복잡도는 O(n)이다.
- 최악
위와 같이 ra가 많이 사용되는 케이스라면 최악의 시간복잡도가 나온다. 최악은 O(N^2)이다.
참고 블로그
https://eeeuns.github.io/2022/04/15/push-swap/
https://80000coding.oopy.io/8bf0d7c1-9fdb-4114-b4e6-59d823b76286
