스택만을 이용한 풀이

Question

선생님의 풀이를 보고 이건 진짜 못떠올릴 것 같은데? 라는 생각이 들었습니다. 배열에 마킹을 하면서 푸는 풀이는 떠올릴 수 있을 것 같은데, 스택만 이용한 풀이에서 -1을 넣어서 풀이하는 방식은 정말 감탄이 나오네요. 저도 스택만을 이용하는 비슷한 풀이를 떠올려서 '((()))'가 6이 나오게 하는 방법은 고안을 했는데 '((()))()'가 8이 되게 하는걸 처리하기가 너무 어렵더라구요. 하지만 -1을 넣어두면 전부 처리가 되네요. 그리고 올바르지 않는 문자열이 오면 그 인덱스를 넣어주면 -1을 넣은 것과 동일하게 뒤의 문자열도 판별할 수 있다니... 이 풀이를 보고 이런 아이디어는 정말 못 떠올릴 것 같다는 생각이 들었습니다. 이런 아이디어를 잘 떠올리기 위해서 어떻게 연습하면 좋을까요?

큰돌 · Answer

안녕하세요 상민님 ㅎㅎ 음.. 우리가 구현해야하는 것에 대해 틀릴 수도 있지만 빠르게 테스팅하는 것에 초점을 맞추면 됩니다. 올바르지 않는 문자열이 오면 그 인덱스를 넣어주면 -1을 넣은 것과 동일하게 뒤의 문자열도 판별할 수 있다니 -> 이거는 저는 이렇게 생각했습니다. 5 - 3 -> 2, 5 - 1 -> 4 까지는 되는데 그 다음 0을 만났을 때 6이 안떨어지더라구요. 그래서 -1을 넣으면 어떨까? 생각해보면 n, n - 1인상태에서 서로 두개를 빼서 2가 나오로면 n - (n - 1)-> 1이 되기 때문에 n - 1에다가 -1을 더 하면 2가 되지 않을까? 즉, -1을 넣으면 해당 부분이 커버가 되는게 아닌가? 생각을 한거죠. 근데 이런 가설은 틀릴 수도 있지만 빠르게 테스팅을 했습니다. -1 넣어보고 아 ((())) 이런게 되네? 자 그럼 여기서 한가지 더 남은 예시가 있죠? ((()))() 이렇게 된다 라고 했을 때 그 다음 괄호에 대한 분기점은 어떻게 만들지 -> stk.push(i) 이런식의 흐름이였던 것 같습니다. 이렇게 stk.pop, stk.top 이런 일반적인 로직에다가 -> 여기서 필요한 부분에 대해 -> 예시를 몇개 맞춰가면서 구현하시면 됩니다. 이런 아이디어를 잘 떠올리기 위해서 어떻게 연습하면 좋을까요? -> 음.. 이문제는 난이도 있었던 문제인데요 ㅎㅎ 어려운 문제를 많이 푸는게 좋습니다. 다만, 제 강의내의 문제에만 일단 집중 -> 그 다음 틀렸던 문제 위주로 해당 유형과 비슷한문제를 푸는 방식으로 진행해주세요 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.