C언어 strcat 함수 : 문자열을 이어 붙인다.

 strcat 함수는 문자열을 이어 붙이는 함수입니다.

 

 

char *str(char *dest, const char *ori);

 

 

 dest에 ori를 붙입니다. 어렵지 않네요? 먼저 시간 복잡도 먼저 분석해 보도록 합시다.

 

 

---

 보통, string 뒤에 붙이는 것은, O(|ori|)인 경우가 많기는 해요. 끝 위치만 알고 있다면, 그 위치에서부터 뒤로 붙여버리면 되거든요. 단, 공간이 충분하다는 전제 하에서요. 물론, Java의 StringBuffer나 StringBuilder 같은 경우에는, 크기가 변할 수 있는, 동적 배열이긴 합니다. 그러니, 공간이 부족하다 싶으면 expand를 호출을 할 거고요.

 

 그러면, 이 친구는 어떻게 동작할까요? 끝 위치를 저장하고 있을까요?

 

 

 이 코드는 단순합니다. str에 계속 "a"를 뒤에 붙이는 프로그램입니다.

 

 

 결과는 어떻게 나올까요? 30만번 "a"를 concat 했더니, 시간 초과가 났습니다. 이건 왜 그럴까요? 분명하게도, 우리는 문자열을 기존의 string 뒤에 붙이는 것을 O(|ori|)에 할 수 있다고 했고, "a"의 길이는 1이니까, 이것을 30만번 하면, 대략 30만번 돌 겁니다. 그러면 시간 내에 돌아갈 거고요.

 

 그런데 왜? 시간 내에 돌아가지 못할까요?

 

 

 어떠한 string 뒤에 다른 것을 붙이기 위해서는, dest의, 그러니까 target의 길이를 알고 있어야 합니다. 그런데, 우리는 따로 그러한 정보를 저장하지는 않았어요. 그리고, 우리가 인자를 넘겨줄 때, dest의 시작 주소를 넘겨 주었는데요. 이 때, 분명히, 노란색으로 칠한 부분까지 널 문자가 등장하지 않았습니다. 그럼에도 불구하고 dest의 전체를 탐색하고 있어요.

 

 

 

 그러면, dest부터, dest+dest_len까지, 그러니까 NULL 문자를 마나기 위해서, |dest|만큼 탐색을 추가로 해야 합니다. 그리고, 노란색 부분에 도달하면, 그 위치부터 |ori|만큼 값을 복사할 거에요.

 

 

 그러면 최종적인 시간 복잡도는 O(|dest|+|ori|)가 될 겁니다. 중요한 것은, 우리는 1+2+...+(n-1)회만큼의 필요 없는 단위 연산을 하고 있다는 것입니다. 예제 1번은요. n이 30만이기 때문에, 그 횟수를 대략 450억 단위. 시간 초과가 날 만 합니다. 이걸 어떻게 개선하면 좋을까요?

 

 

 당연하게도, 같은 문자열 뒤에 계속 concat 하려는 경우, 길이를 저장하고 있으면 됩니다.

 

 

 예제 2번 프로그램은 예제 1과 완벽하게 같은 일을 합니다. 다만 다른 것은, 뒤에 string을 붙여넣기 할 문자열의 길이에 대한 정보를 계속 저장했다는 것입니다. strcat은 어떻게 동적했나요? target의 길이를 구한 뒤에, 그것의 뒤부터 붙여넣기를 합니다.

 

 

 

 그러면 결론적으로 str+len에다가 계속 붙여넣을 문자열 pat을 넣어주면 될 거에요. 그 다음에 len은 |pat|만큼 증가하면 될 거고요. 길이값을 가지고 있어야 한다는 것이 핵심이라면 핵심이라 할 수 있겠습니다.

 

 

---

 dest와 source가 overlap 되지 않아야 한다는 조건도 있습니다. 예를 들어서, 이런 경우입니다.

 

 

 위에 있는 코드를 봅시다. 여기서 dest는 str+1, ori는 str입니다. 이를 각각 노란색과, 보라색으로 표시해 봅시다.

 

 

 둘이 서로 겹친다는 것을 알 수 있어요. 그러면 구현체에 따라서, 무한 루프를 돌 수 있어요. 어떻게 구현을 했을 때, 무한 루프가 돌 수 있는지는 조금만 생각해 보시면 쉽게 간파하실 수 있을 테니, 그 부분은 자세히 설명드리지는 않겠습니다. 힌트만 하나 드리자면, 이러한 경우, 특정한 방식으로 구현하면 ori도 변형이 일어난다는 것입니다.

 

 

  한 가지 결정적인 힌트를 드리자면, 이런 식으로 구현했을 때, 문제가 발생하는데요. 보시면, dest가 가리키는 곳도 변형이 가해지고 있어요. 그렇게 때문에 계속 무한루프가 돌다가, 메모리 공간을 잘못 건드리면 터지는 겁니다. 물론, 환경에 따라서, 정상적으로 나오는 경우도 있을 거에요. 미리 dest (붙여 넣을 string)의 길이값을 저장하는 식으로 회피할 수는 있을 건데, 환경에 따라 다르게 구현이 되었을 수도 있어요.

 

 이러한 부분은 조심해야 한다는 것만 알아두시면 좋겠습니다.

 

 

 

 또 하나. 당연하게도, strcat는 경계 검사를 하지 않습니다. 그렇기 때문에, dest는 ori가 뒤에 붙여질 만큼 충분한 공간이 있어야 한다는 것입니다. 예를 들어서, 현재 dest에 "abcdefg"가 저장이 되어 있습니다. 그리고 우리는 "at"을 10번 붙여넣으려고 합니다. 그러면, 최소한 dest는 7 + 2*10 + NULL문자를 저장할 공간 = 최소 28개의 char형을 저장할 수 있어야 한다는 것입니다.

 

 

 이제 예제를 하나 봅시다. str에는 "cho"가 저장이 되어 있습니다. 저는 str에 어떤 것을 붙여 넣었나요? 처음에는 "ga", 두 번째에는 "hi", 세 번째에는 "05"를 붙여넣었습니다.

 

 

 실행 결과는, 제가 백준 사이트에서 쓰는 닉네임이 나옵니다.