kkw564   9달 전

어디가 틀린걸까요.. 정확히 모르겠습니다 테스트 케이스 하나만 주시면 감사하겠습니다

음.. 문제에 제시한 방법에 대한 풀이는 아니지만

 그냥 \0이 아닌 ' '등의 공백으로 바꾸어주면서 len에서 1씩 빼주고

len이 0이면 문자열 출력, 아니면 for문 돌려서 출력할때 공백일 때 continue 하는게 더 효율적일 것 같습니다.

잦은 strcat이 시간 초과가 날 수도 있을 것 같아서요

아 밑에 자체가 덩어리였군요 ㅋㅋ 1글자 1글자씩 덩어리라는줄.. 제가 문제 이해를 잘못했네요 풀어보고 다시 댓글달게요

1C4C4C4ddd

C4d

이면

1C4C4C4ddd -> 1C4C4dd-> 1C4d -> 1이 남아야 되는데

위 소스는 1C4C4dd가 출력되네요

kkw564   9달 전

if(check == 1)
     {
      i--;
      check = 0;
     }

이부분에서 i = i - lenB;로 고쳐서 테스트케이스 합격나왓는데 또 돌리니 틀렸습니다뜨네요.. ㅋㅋㅋㅋㅋ

indioindio   9달 전

lenA 도 적절히 업데이트 되어야 하지 않나요?

lenA도 바뀌어야겠죠

kkw564   9달 전

if(check == 1) 
     {
      i = i - lenB; 
      lenA = lenA - lenB;
      check = 0;
     }


이구문 틀린건가요?? lenA를 생각해서 대입했는데 계속틀렸다나와서그런지 감이 계속없어지네요..

indioindio   9달 전

C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4C4
C4C

에 대해서

44444444444444444444444444444444444444444444444444C4

를 출력해야 하는데 다른 값을 출력하네요

어딘가 인덱스가 하나 틀린 것 같네요 ㅠㅠ

kkw564   9달 전

코드해결같이종도와주실수있을까요?

indioindio   9달 전

확인해보니 strcat의 src와 dst가 부분적으로 겹치면 문자열의 내용이 변하는 undefined behavior가 생기는 것 같네요.

memmove등을 이용해서 문자열의 일부분을 지우고 다시 합하는 걸 구현할 수도 있는데, 그러면 아마 시간초과가 날 것 같습니다.

원래 strcat으로 구현해도 합 할 때마다 두 문자열의 길이의 합 만큼 걸려서 아마 시간초과가 나야할텐데 문자열이 변해서 대신 오답이 났나 봅니다.

다른 방법을 찾아보셔야 할 것 같네요.




kkw564   9달 전

strcat는 공식적인 함수인데 그 함수를 이용하면 undefined behavior이 생기나요??


그리구 위에 c4c4~~~c4

c4c


저입력과 출력은 정상출력되는것같은데요 음..

strcat가 잘못됫다는건가요 아니면 제코드가 잘못됫다는건가요./.

indioindio   9달 전

음 저 코드에서 댓글에 말씀하신대로

if(check == 1) 
     {
      i = i - lenB; 
      lenA = lenA - lenB;
      check = 0;
     }

로 수정한 코드에서 실행하면 오답을 출력하는 것 같은데 제 수정본이 조금 다를 수도 있겠네요.

네. strcat매뉴얼에 보시면 src와 dst가 겹치면 undef. behavior가 생길 수도 있다고 되어 있습니다.

strcat을 이용해서 문자열의 일부분을 지우고 다시 붙이는 과정에서 오답이 나게 됩니다. (이 용도로 strcat을 사용하면 안 될 것 같네요)

kkw564   9달 전

#include <stdio.h>
#include <string.h>
 
char a[1000005];
char b[40];
char c[40];
int main()
{
    int i,lenA,lenB;
    int check = 0;
     
    scanf("%s",a); // 문자열을 받고 
    scanf("%s",b); // 폭발 문자열을 받고 
     
    lenA = strlen(a); // 길이를 측정 
    lenB = strlen(b);
 
 
     
    for(i = 0 ; i < lenA ; i ++) 
    {
     if(check == 1) 
     {
      i = i - lenB; 
      if(i < 0) i = 0;
      lenA = lenA - lenB;
      check = 0;
     }
     if(strncmp(a+i,b,lenB) == 0)
     {
       a[i] = '\0';      
       strcpy(c,a+i+lenB);
       strcpy(a+i,c);
      i --;                      
      check = 1;
     }
      
      
    }
     
    if(a[0] == '\0')
    {
     printf("FRULA");
     return 0;
    }
 
         printf("%s",a);
         return 0; 
      
     
}


이렇게 다시 코드 짜봤는데 이건 시간초과가뜨네요.. 왜그런걸까요 ㅠㅠㅠ

indioindio   9달 전

음 strcpy는 대상 문자열의 길이 만큼 시간이 걸려서 원래 이 문제에서 폭탄문자열 삭제하고 붙이기를 반복하면 시간초과가 나게 됩니다.

그리고 c배열을 버퍼삼아서 strcpy를 하셨는데 a+i+LenB의 남은 문자열의 길이가 40미만이라는 보장이 없어서 문자열이 제대로 복사되지 않고, segfault가 날 수도 있습니다.

kkw564   9달 전

이건 결국 스택으로 푸는것 아니면 안되는걸까요.. ㅋㅋ

계속여쭤봐서 죄송합니다.

indioindio   9달 전

ㅋㅋㅋ아닙니다.

네 지금 당장은 저 알고리즘을 유지하면서 시간 내에 들어올만한 뾰족한 방법이 생각나지는 않네요.

통과한 코드 중에는 한 번에 없앨 수 있는 문자열을 전부 없앤 다음 나머지 문자열들을 붙이고를 반복하는 코드도 있던데 c의 문자열 처리함수들로는 어려울 것 같네요. (그 코드는 파이썬이었습니다.)

kkw564   9달 전

 저도 파이썬코드는봤는데 되게 간단명료하더라구요.. ㅋㅋ 저도 계속 생각해본 뒤 여기서 답변드리겠습니다.


감사합니다 ㅠㅠ

indioindio   9달 전

개인적으로는 일단 스택으로 푸시는 게 간단하지 않을까 싶네요

indioindio   9달 전

제가 위에서 말씀드렸던 파이썬 코드를 c에서도 구현해봤더니 44ms에 통과하네요.

포문으로 a문자열을 보면서 strncmp해서 결과가 같은 게 있다면 pos배열에 폭탄문자열의 시작위치를 저장한후에,

a문자열을 다시 훑으면서 pos배열에 들어있는 위치에 올 경우 스킵하면서 글자들을 왼쪽으로 복사했습니다.

그런데 이런 식으로 구현하면

CC.......4444....

C4

와 같은 입력에 대해서 매번 a의 문자열의 길이가 2씩만 줄어서 시간이 꽤 오래 걸리게 되는데(위의 파이썬 코드도 마찬가지구요)

테스트케이스에는 그런 예제가 없어서 스택기반의 알고리즘보다 더 우수한 성능을 보이는 것 같네요.

댓글을 작성하려면 로그인해야 합니다.