제목. 왜 10시간동안 아래 코드가 잘못된 동작을 하는 원인을 찾았는가? 제목이 꽤나 성가실 지도 모르겠습니다만, 오늘 몇 시간동안 삽질한 주제였습니다. 자신의 코드는 잘 안 보인다고 하는데, 그 말이 딱 맞았습니다. 심지어 고인물들이 모여 계시는 알고 싯포 톡방에서, const char * 문제인가? 를 가지고도 간접적으로 질문을 했는데, 실험도 해 보고, 이것 저것 팁들을 들어보니, 이것도 답이 아니였습니다. 당연하게도, 제가 완전히 잘못 파악한 것이였습니다. 부들부들 해당 문제를 풀기 위한 코드를 보도록 하겠습니다.

 


 먼저, dp 함수는 아래와 같습니다.

 

 for loop를 돌면서, temp에 app(i, x-i)를 수행한 결과물인 string의 c_str()의 주솟값을 넣습니다. 그리고, temp와 mmn을 비교해서, 조건을 만족하면, mmn에 temp의 값을 집어 넣습니다. 그리고 for loop를 돌고 최종적으로 ans[x]에 답을 넣습니다.

 

 

 app 함수는 그리 복잡하지 않습니다. ans[lo1]과 ans[lo2]를 append 시켜서 리턴합니다. 더 간단하게 쓰려면, ans[lo1] + ans[lo2]해도 크게 문제는 없어 보입니다. 실행을 시켜 봅시다.

 

 

 이상한 값이 나와버립니다. 대체 무엇이 문제일까요? 하나 확실한 것은, c++의 string은 내부적으로 char형 배열을 가지고 있고, expand 연산이 지원되는 일종의 동적 배열이라는 겁니다. 그러면, 이런 추측을 해 볼 수 있습니다.

 

 

 "aab"가 string에 저장이 되어 있습니다. 여기서 문자를 엄청나게 넣어서, expand 연산이 일어났다고 해 보겠습니다.

 

 

 그러면, 이전에 있었던 c_str()에 관한 정보, 즉 군청색 배열을 가리키는, 정보는 유효하지 않게 됩니다. 왜냐하면, 확장되는 과정에서 delete가 되었을 것이고, 이미 string의 내부에 있는 실제 문자열을 가리키는 포인터는 다른 곳을 가리키기 때문입니다. 만약에, 이전의 포인터를 가리키고 있다면, valid하지 않은 곳을 가리키고 있다는 의미가 됩니다. 이를 dangling pointer라고 합니다. 실제로 그런지 테스트를 해 보겠습니다.

 

 프로그램은 간단합니다. "abcdefg"를 저장하고 있는 string s를 생성합니다. 그리고, s.c_str()의 값을 str이 가리키게 합니다. 다음에, s에 제 아이디를 append 시킵니다. 결과는 어떻게 나올까요?

 

 

 중간에 확장이 되었다면, str은 유효하지 않은 곳을 가리킬 겁니다. 왜냐하면, 확장이 될 때, 기존에 있었던 배열은, 무의미하기 때문입니다. 설령 delete가 되지 않았다고 해도요. 이것을 그림으로 나타내면 아래와 같습니다.

 

 

 군청색 부분은 이미 회수되거나, 쓸모가 없어진 공간이고, 이것을 const char *str이 가리키고 있습니다.

 


 그러면, 제가 문제를 풀기 위한 작성한 코드는 어디서 문제가 있었을까요?

 

 간단하게, 위와 같이 클래스를 작성해 보겠습니다. A의 소멸자가 호출되면 destroy가 출력됩니다.

 

 문제에 있던 코드와 비슷하게 작성해 보겠습니다. for loop를 돌면서, 지역변수 b를 새로 선언하였습니다.

 

 

 destroy가 3번 호출되었다는 것은 생각보다 중요합니다. 이는 함수에서 1번 선언된 지역 변수, for loop에서 2번 선언된 지역변수가 scope를 벗어났기 때문입니다. 그러면, 이게 문제일 수도 있을까요? string도 그럴까요?

 

 

 간단하게 for loop를 돌 때 마다, c_str()이 어떻게 변하는지 보면 될 듯 싶은데요.

 

 

 제가 돌린 환경에서는 loop를 돌릴 때마다 temp 값이 같음을 볼 수 있습니다. 상황을 유추해 보면, 루프를 돌 때 마다, 실제 문자열을 들고 있는 위치가 바뀌지 않았습니다. 만약에, 이전 string이 valid 했다면, 실제 문자열을 들고 있는 위치가 같지는 않았을 겁니다. 최소한, 이전, 옛날의 string, temp가 valid 하지 않았다는 의미입니다.

 

 그렇게 된 시점은, app 함수에서 string을 돌려주고 난 직후일 겁니다. app 안에 있는 string은 유효 범위에서 벗어나게 되는데, 유효하지 않은 위치를 temp가 가리키고 있게 됩니다. 어떻게 하면 될까요? 결과 값을 copy 해서 가지고 있으면 됩니다. 없어져서 유효하지 않게 될 포인터를 가지고 있는 것이 아니라.

 

 


  내용 복사가 되는지, 얕은 복사가 되는지는 쉽게 예제를 작성할 수 있습니다. 프로그램 3을 보겠습니다.

 

 내용 "abcde"를 들고 있는 string t를 선언하였습니다. 그리고, s에 t를 assign 하였습니다. 다음에, t[2]에 'C'를 넣었습니다. 얕은 복사가 되었다면, 둘 다 "abCde"가 나왔을 겁니다.

 

 

 중요한 것은 t만 "abCde"가 나오고, s는 "abcde"가 나왔다는 것입니다. 그러면 아래와 같이 작성하면 어떻게 되나요?

 

 result 값을 복사하고, temp값을 경우에 따라서 mmn에 복사를 합니다. 그러면, temp가 유효하지 않게 되더라도, 이미 필요로 하는 경우에 실제 값을 mmn에 복사했기 때문에 17623번 문제를 푸는 데에 큰 문제가 없습니다. 방어적 복사라고 이야기 하는지, 뭐라고 하는지는 잘 모르겠네요. 이 부분은 링크에서 꽤 자세히 언급하고 있으니, 참고 하시는 게 좋겠습니다. 저만 실수한 게 아닌가 봅니다.

 

 

 그리고 chk 함수 또한 string 2개를 받아서 처리하는 것으로 개선하였습니다. 이런 식으로 코딩하면 보다 깔끔하게 17623번을 풀 수 있습니다. 문제의 코드개선된 코드는 링크로 걸어두겠습니다.

댓글을 달아 주세요