안녕하세요? 본 문제는 스택 자료구조를 이용하여 푸는 것을 추천드립니다. 첨부해주신 코드의 논리대로라면, 이런 문자열이 나오면 카운트를 증가시켜야 겠죠:

문자열 탐색 도중 '{{' 을 만나면 카운트 1 증가
문자열 탐색 도중 '}}' 을 만나면 카운트 1 증가
문자열 탐색 도중 '}{' 을 만나면 카운트 2 증가  

하지만 이 논리의 경우 아래와 같은 반례가 생기게 됩니다:

 입력:
{{}}
---
정답:
0
출력:
2

문제의 1번 조건과 2번 조건에 따르면 빈 칸은 안정적인 문자열이고, 빈칸에 괄호를 씌운 것도 안정적인 문자열이므로 '' -> '{}' -> '{{}}' 은 안정적인 문자열입니다. 따라서 정답은 0이어야 합니다.

같은 '{{' 가 쓰였다 할지라도, '{{' 뒤에 어떤 괄호가 오느냐에 따라 안정적인 문자열일수도 있고, 아닐 수도 있기 때문에 스택 자료구조를 이용해 이전에 입력되었던 괄호를 저장해 두면서 문제를 푸는 방식을 추천드립니다. 예를 들어, 반례인 {{}}의 경우 '{' 가 2번 오면서 스택에 '{' 가 두 번 저장되고, 이후 '}' 가 올 때마다 가장 최근에 저장되었던 '{' 가 하나씩 상쇄되는 식으로 문제를 풀면 남은 '{' 는 없게 되므로 모든 괄호가 짝을 이루었음을 짐작할 수 있습니다.

'{{' 뿐만 아니라 '}{', '}}' 도 상황에 따라 안정적인 문자열인지 아닌지가 달라지므로 문제를 푸는 데 있어서 유의하시기 바랍니다.

문제 해결에 도움이 되었으면 좋겠습니다.

다음과 같은 코드로 바꿨는데..잘안풀리네요..뭐가 잘못된 건지 모르겠ㅇ어요..

해당 코드에서 드릴 수 있는 반례입니다:

입력:
}}}{
---

정답:
1. 3

출력:
1. 2

}}를 {} 로 바꾸고, }{를 {} 로 바꿔야 하므로 정답은 3입니다. 3보다 적은 횟수를 사용하여 안정적인 문자열을 만들 수 있는 경우는 없습니다.

제가 찾은 문제는 3가지이고, 제 논리대로 내린 결론이기 때문에 질문자님의 의도와는 다를 수도 있음을 미리 알려드립니다. 일단 확실한 것은 모든 문제는 return_sum() 에서 답을 구하는 과정에서 발생했다는 것입니다.

1. j값을 증가시키면서 '{', '}' 를 확인하는 과정에서 웬 문자열 'P' 가 0번 인덱스에 들어 있습니다.

제가 C, C++를 할 줄 모르므로 왜 그런지는 설명해드릴 수 없습니다. 만약 이 질문을 C를 쓰시는 분이 보고 계신다면 답변해 주시면 좋을 것 같습니다. 어쨌든 디버깅 과정에서 'P' 가 괄호 검증을 방해하고 있었습니다. 예를 들어 '{}}{' 가 주어졌다면:

P {
{ }
} }
} {

이런 식으로 괄호가 검증되고 있습니다. 확인 후 검사하는 인덱스를 적절히 조절하시면 될 것 같습니다.

2. j가 1씩 증가하고 있습니다.

검사하고 있는 괄호는 두 개씩인데, 검사할 괄호의 인덱스를 결정하는 j가 1씩 증가한다는 것은 곧 같은 괄호가 겹쳐서 검사될 수 있음을 의미합니다. 질문자님의 의도를 잘 모르겠지만, 아마도 '{{', '}}' 와 '}{' 를 구분하여 처리하려고 하셨던 것으로 보입니다. 이 경우 괄호를 두 개씩 끊어서 검사해야 할 것으로 보이고, 증가되는 j의 값도 달라져야 할 것 같습니다.

3. 반복문의 종료 조건이 변동될 수 있습니다.

이게 무슨 뜻이냐고 물으신다면, 아래의 반복문에 주목해 보세요:

for (int i = 1; i <= 10; i++) {
    printf("%d\n", i);
}

이 반복문은, 10번 반복하고 종료되는 것이 확실한 반복문입니다. 즉 반복문의 종료 조건이 항상 i <= 10인 동안이며, 반복문이 진행되는 동안 이 조건이 유지되는 것이 확실하게 보장됩니다. 이제 적으신 반복문에 주목해 보세요:

for (int j = 0; j <= pstack->topindex; j++){
        if((pstack->arr[j] == '{' && pstack->arr[j+1] == '{' )|| (pstack->arr[j] == '}' && pstack->arr[j+1] == '}')) {
             pstack->topindex = pstack->topindex - 1;
        }
}

종료 조건이 j <= pstack -> topindex 인데, 반복문 내부에 pstack -> topindex가 감소하는 코드가 있죠? 즉 반복문이 진행되는 동안 감소하는 코드가 실행되기라도 하면, 종료 조건이 바뀌어서 의도와는 다르게 동작할 수도 있다는 뜻입니다. 위 코드의 경우에는 원래보다 값이 작아져 모든 괄호를 검사하기도 전에 반복문이 종료되는 일이 일어날 수도 있게 되겠지요. for문의 종료조건을 입력하실 때는 주의하셔야 합니다.

이에 대한 해결책으로 반복문이 시작되기 전 미리 pstack->topindex 값을 새로운 변수에 저장한 후, 그 새로운 변수를 종료 조건에 사용하면 될 것 같네요. 중간에 pstack->topindex 값이 바뀌더라도 새로운 변수의 값은 항상 일정할 테니까요.

이상이 질문자님의 코드를 디버깅 해 본 후 문제라고 생각한 부분을 적은 것입니다. 좀 난해할 수 있겠지만, 조금이나마 도움이 되었으면 좋겠습니다. 이 답변은 질문자님의 코드를 올바르게 수정해서 맞았습니다!! 를 받은 후 적은 답변이니 너무 걱정하지 마세요. 좀 더 시도해 보시고, 그래도 해결이 안 된다면 다시 댓글로 적어주세요. 힌트를 더 제공해 드리겠습니다.

정말 감사드립니다! 첫번쨰로 j값이 증가하면서 확인하는 과정에서 p가 왜 들어있는지는 도저히 모르겠네요..

두번째로 말하셨던 j값의 증가 범위도 감사드립니다.(제가 왜 j를 1씩 증가시켰는지 모르겠네요..2씩 증가시키는게 맞는건데..)

세번쨰로 반복문의 종료조건 말씀하신것도 감사드려요. 앞으로 코드를 작성할떄 이런 사태가 일어나지 않도록 주의해야겠네요..

정말정말 감사드립니다!!