fryste hjertet

1번 따위 넘어가고, 2번부터.

일단 문자열의 위치와 길이를 관리하기 위해 구조체를 정의하였다.

typedef struct str
{
 int startindex; //문자열 시작위치
 int endindex; //문자열 끝 위치
 int length; //문자열 길이
}str;
/*
기본 구조는 이렇다. 앞에서부터 문자열을 탐색하며 연속된 문자열을 찾는다. 문자는 ASCII코드 등을 따른다는 전제 하에, (s[i]+1==s[i+1]) 같은 수식으로 문자열의 연속을 감지할 수 있다. 만약 연속된 문자열을 찾게 되면, 그 연속 규칙이 어디까지 적용되는가, 다시말해 (s[i]+1==s[i+1]) 라는 수식이 적용되는 부분이 어디까지인가를 별도로 알아낸다. 한 문자열 부분의 처음과 끝 위치를 알아냈다면, 끝 위치-시작 위치 = 문자열 길이 가 성립할 것이다. 이 세 정보를 아까 정의한 구조체에 담은 후, 이 구조체를 스택에 저장한다. 여기에 사용한 스택의 내부구조에 대한 설명은 생략한다. (구현 코드는 하단 첨부)
*/
int cal(char *s, int length)
{
 stack stack1, stack2;
 struct str mystr;
 bool flag=false;
 for(int i=0;i<length;++i)
 {
  
  if((s[i]+1==s[i+1]) && flag==false)
  {
   mystr.startindex=i;
   flag=true;
  }
  else if((s[i]+1 != s[i+1]) && flag==true)
  {
   mystr.endindex=i;
   flag=false;
   mystr.length=mystr.endindex-mystr.startindex+1;
   stack1.push(mystr);
  }
 }

/*하나의 스택에 이렇게 연속된 문자열들의 구조체 정보들이 모두 담기게 되면, 중복되는 것만 추출할 차례다.
스택 내부의 원소들을 서로 비교해서 중복되지 않는 것들을 모두 제거한다. 원래 스택을 링크드리스트로 구현하여 삽입, 삭제에 용이하게 하는 것이 좋겠지만, 한페이지로 제한된 시험지 지면의 한계상(...) 간단한 배열을 사용하였다.
*/

  int ret=0;
 for(i=0;i<stack1.count();++i)
 {
  int ret=0;
  struct str mys=stack1.getter(i);
  for(int j=0;j<stack1.count();++j)
  {
   struct str mys2=stack1.getter(j);
   if(!strncmp(&s[mys.startindex], &s[mys2.startindex], mys.length)  && (mys.startindex != mys2.startindex )&& mys.length!= 0)
   {

    mys.length=0;
    ret++;
   }
  }
  if (ret==0)
  {
   stack1.setDelete(i);
  }
 }

//중복되지 않은 것을 제거했다면, 최대값을 추출하면 된다. 최대값 구하는 알고리즘은 정형화되어 있다. 다만 문제에서 요구하는 출력값은 최대 길이 자체가 아니라, 해당 문자열의 시작위치이므로 startindex를 찾아낸다.

 int max=0;
 int sindex=0;
 for(i=0;i<stack1.count();++i)
 {
  struct str ss=stack1.getter(i);
  if(max<=ss.length)
  {
   max=ss.length;
   sindex=ss.startindex;
  }
 }
 return sindex;

}

//이 프로그램을 구동시킬 메인함수는, 문자열을 간단히 넘겨주면 된다. 아래 문자열 대로 하면 결과값은 14가 나온다.
int main(int argc, char *argv[]) {

 char *ary="abcdefaaabeabcabcdeabcjjjab";
 int result=cal(ary, strlen(ary));

 printf("%d", result);

 return 0;
}

//아래는 자료구조로 사용한 간단한 스택이다. 크게 특별한 것은 없다.
class stack
{
public:
 stack()
 {
  sp=0;
  c=NULL;
 }
 void push(struct str mys)
 {
  if(c==NULL)
   c=new struct str[1];
  else
  {
   struct str *temp=new struct str[sp+2];
   memcpy(temp, c, sizeof(struct str)*(sp));
   delete c;
   c=temp;

  }
  c[sp].startindex=mys.startindex;
  c[sp].endindex=mys.length;
  c[sp].length=mys.length;
  sp++;

 }
 struct str getter(int i)
 {
  if(sp>=i)
  {
   return c[i];
  }
  else
  {
   struct str a;
   return a;
  }
 }

 int setDelete(int i)
 {
  if(sp<=i)
   return 0;
  else
  {
   c[i].startindex=0;
   c[i].endindex=0;
   c[i].length=0;
  }

 }
 int count()
 {
  return sp;
 }
 int sp;
 struct str *c;
};

문제에는 문자열 최대길이를 1000으로 제한하였으나, 본 알고리즘은 문자열 길이에 제한없이 사용이 가능하다.

2번 설명은 이쯤 하고, 3번.

숫자의 포인터를 받아 옆 숫자와 비교하는 함수이다. 원래라면 바운더리에 관련한 예외처리를 해주어야 하나, 지면상 생략하였다.

int *cmp(int *a, int *b, int *c)
{
 if(a[1]-a[0] >= c[1]-c[0] && b[1]-b[0] >=c[1]-c[0])
  return c;
 else if(a[1]-a[0] >= b[1]-b[0] && b[1]-b[0]<= c[1]-c[0])
  return b;
 else if( a[1]-a[0] <= b[1]-b[0] && a[1]-a[0] <= c[1]-c[0])
  return a;
 else
  return a;
}

// 전체 배열을 총 3 부분으로 나눈다. 사실 두 부분으로 나누든 세 부분으로 나누든 네 부분으로 나누든 별 상관은 없다.

int *cal(int s[], int length)
{
 int *a, *b, *c;
 if(length>3)
 {
  a=cal(&s[0], length/3);
  b=cal(&s[length/3], length/3);
  if(length%3==0)
  {
   c=cal(&s[length/3*2], length/3);
  }
  else
  {
   c=cal(&s[length/3*2], length/3+1);
  }
 }
 else if(length==3)
 {
  a=&s[0];
  b=&s[1];
  c=&s[2];
 }
 else
 {
  return &s[0];
 }
 return cmp(a, b, c);
}

//계산결과로 나온 숫자들을 출력하는 함수

void print(int s[], int length)
{
 int *a=cal(s, length);
 printf("(%d, %d)", *a, *(a+1));
}

//메인함수. 아래 값대로 하면 결과값은 (44, 45)가 나온다.

int main()
{
 int s[12]={1, 4, 6, 8, 11, 13, 15, 18, 21, 25, 44, 45};
 print(s, 12);
 return 0;
}

사실 예외처리도 안한 부분이 많고, 좀더 시간을 들였다면 더 잘 쓸 수도 있었겠군요. 역시 한시간만에 뛰쳐나오는 게 아니었나보죠..(...) 일단 집에서 그대로 돌려보니 다 제대로 돌아가긴 합니다만, 3번같은 경우 예외처리가 별로 없다는 게 흠이군요.

뭐 그래봐야 떨어진 마당에 어쩔..OTL


...근데 다른사람들은 대체 얼마나 잘 풀었길래..