C언어 212제] 팬 케이크(Stacks of Flapjacks)

출처 : 반크_백제역사 유적지구와 이스탐블역사 유적지구

 

문제]

그릴에서 팬 케이크를 구워서 완벽한 팬 케이크 스택을 만드는 것은 정말 까다로운 일이다. 아무리 팬 케이크를 정성스럽게 만들어도 팬 케이크의 크기가 조금씩 다르기 때문이다. 하지만 팬 케이크를 잘 정렬해서 위에 있는 팬 케이크가 아래에 있는 팬 케이크보다 더 작게 쌓으면 깔끔하게 보이게 할 수 있다. 팬 케이크의 크기는 그 지름으로 주어진다.

스택을 정렬하는 과정은 일련의 팬 케이크 뒤집기 작업을 통해 이루어진다. 한 번 뒤집는 작업은 스택에 쌓여있는 것 중 두 팬 케이크 사이에 주걱을 집어넣고 그 주걱 위엥 있는 모든 팬 케이크를 뒤집는 작업(주걱 위에 있는 팬 케이크로 두성된 하위 스택의 순서가 거꾸로 되도록 만드는 작업)으로 구성된다. 한 번의 뒤집기 작업은 전체 스택을 기준으로 뒤집어질 하위 스택의 맨 아래에 있는 팬 케이크의 위치를 지정하는 방식으로 표시된다. n개의 팬 케이크로 구성된 스택이 있을 때 맨 밑에 있는 팬 케이크의 위치는 1, 맨 위에 있는 팬 케이크의 위치는 n으로 표시된다.

스택은 팬 케이크가 등장하는 순서대로 스택에 들어있는 각 팬 케이크의 지름을 알려주는 식으로 열거된다. 예를 들어 다음은 세 개의 팬 케이크 스택을 열거해 놓은 것인데, 왼쪽 스택 맨 위에 있는 팬 케이크는 지름이 8임을 알 수 있다.

8     7     2
4     6     5
6     4     8
7     8     4
5     5     6
2     2     7

flip(3)을 통해 왼쪽 스택이 가운데 스택으로 바뀔 수 있다. 그리고 flip(1)이라는 명령을 쓰면 가운데 스택이 오른쪽 스택으로 바뀐다.

입력
입력은 여러 개의 팬 케이크 스택으로 구성된다. 각 스택은 한 개에서 서른 개 사이의 팬 케이크로 구성되며 각 팬 케이크의 지름은 1이상 100이하의 정수로 주어진다. 입력은 파일 끝 문자에 의해 종료된다. 각 스택은 한 줄에 입력되며 맨 위에 있는 팬 케이크가 맨 앞에, 맨 밑에 있는 팬 케이크가 맨 뒤에 입력되고 모든 팬 케이크는 스페이스에 구분된다.

출력
각 팬 케이크 스택에 대해 원래 스택을 한 줄로 출력해야 하며 다음 줄에는 가장 큰 팬 케이크가 맨 밑으로, 가장 작은 팬 케이크가 맨 위로 올라가도록(팬 케이크가 클수록 밑으로 가도록) 스택을 정렬하기 위해 필요한 뒤집기 순서를 출력해야 한다. 뒤집기 순서를 출력한 후 맨 뒤에는 더 이상 뒤집지 않아도 된다는 것을 나타내는 0을 출력해야 한다. 스택 정렬이 끝나면 더 이상 뒤집지 않는다.

입력 예
1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

출력 예
1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 26 팬 케이크(Stacks of Flapjacks) p121

 

참고풀이]

#include <stdio.h>
#include <string.h> //strlen()
#include <stdlib.h> //atoi() 
                   
int main()
{
   char Str[100]={'\0'};
   int N=0;
   int Stack[30]={0};
   int i,j,k;
   int tmp;
   char pt[10];

   while(!feof(stdin))
   {
      //줄단위로 자료를 입력받는다.
      if(!gets(Str)) break;

      //입력 받은 자료를 출력한다.
      printf("%s\n",Str);

      //입력 받은 자료를 숫자들로 나눈다.
      for(N=0,j=0,i=0;i<strlen(Str);i++)
      {
         if(Str[i]==' ')
         {
            pt[j]='\0';
            Stack[N++]=atoi(pt);
            j=0;
            pt[0]='\0';
         }
         else
         {
            if(Str[i]>='0' && Str[i]<='9')
               pt[j++]=Str[i];
            else
               return 0;
         }
      }
      if(Str[strlen(Str)-1] != ' ')
      {
         pt[j]='\0';
         Stack[N++]=atoi(pt);
      }

      //스택의 가장 아래쪽부터 케이크를 뒤집기하여 오름차순으로 자료를 넣는다.
      for(i=N-1;i>=1;i--) 
      {
         k=i;
         for(j=0;j<i;j++)
         if(Stack[k]<Stack[j]) k=j;

         if(k<i)
         {
            if(k>0)
            {
               printf("%d ",N-k);
               for(j=0;j<=k/2;j++)
               {
                  tmp=Stack[j];
                  Stack[j]=Stack[k-j];
                  Stack[k-j]=tmp;
               }
            }
            printf("%d ", N-i);
            for(j=0;j<=i/2;j++)
            {
               tmp=Stack[j];
               Stack[j]=Stack[i-j];
               Stack[i-j]=tmp;
            }
         }
      }
      printf("0\n");
   }
   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을