zeta050525   2년 전

예제입력은 다 맞는데 도대체 뭐가 문젠질 모르겠습니다.

Stack을활용해서 풀어봤는데 뭐가 문제일까요ㅠㅠㅠ

20분동안 코드만 봤는데도 모르겠습니다.

wizardrabbit   2년 전

안녕하세요? 반례 드립니다:

입력:
[)]
.

정답:
no

출력:
yes

틀린 이유는 스택에서 괄호가 올바르게 열리고 닫혔는지를 판단하는 코드가 약하기 때문입니다. ")" 가 왔을 때 스택의 마지막 원소가 "[" 일 경우는 균형잡힌 문자열이 아닌 것으로 처리해야 합니다. "[)" 에서 ")" 와 짝지을 수 있는 "(" 가 생길 수 없기 때문입니다(짝지을 수 있는 "(" 는 "[" 보다는 나중이어야 가능하겠지요). 이는 "]" 가 왔을 때에도 동일합니다. 해당 조건을 고려하여 조건을 추가해 주시면 문제를 해결할 수 있을 것입니다.

반례가 입력되었을 때 코드가 어떻게 균형잡힌 문자열을 판단하는 지도 적어두겠습니다. 참고하시기 바랍니다.

"[" , 스택: 【[】
")" , 스택이 비어 있지 않으므로 PASS
"]" , "[" 와 짝지어지므로 스택 pop, 스택 : 【】

결과적으로 스택은 비었으므로 yes를 출력하지만, 실제로 )로 인해 균형잡힌 문자열이 아니게 되므로 no를 출력해야 함을 알 수 있습니다.
")" 가 입력되었을 때 스택을 고려해 "[" 가 있을 경우 바로 return "no" 해야 합니다

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